講義ノート４：動的計画法
稲葉 大
J3 15, 2010 @ G E-mail: big.rice.plant.leaf@gmail.com http://sites.google.com/site/masaruinaba/
I. 動的計画法 (dynamic programming): 有限
期間
中央計画者問題
max
ct,kt+1
∑T t=0
βtu(ct) subject to
kt+1−kt = f (kt) − ct−δkt fort = 1, 2, · · · , T, k0 = k0
kT +1 ≥0.
ここで0 < β < 1 は，割引因子(discount factor)である．効用関数 u(·) と生産関数 f (·) は，
u(0) = 0, u′(·) > 0, u′′(·) < 0, u′(0) = ∞, u′(∞) = 0 f (0) = 0, f′(·) > 0, f′′(·) < 0, f′(0) = ∞, f′(∞) = 0 と仮定する．
ベルマンの最適性の原理
問題の再帰的な(recursive)な構造を利用して解く． 動的計画法は，以下の原理に基づいて考察する．
ベルマンの最適性の原理 (B ’ )
最適政策とは，最初の状態や決定がどうであっても，それ以後の 決定が最初の決定によって生じた状態に関して最適政策となるよ うに構成しなければならないという性質を持っている．(西村 (1994)P150より抜粋)
後ろ向き帰納法(backward induction method)で求めた解は， あるt 時点を考えるとき，それ以降の政策は常に最適になって いる．
時間が有限であるときには，後ろ向き帰納法(backward
induction method)により最適政策得られる．
I.1 後ろ向き帰納法 (backward induction
method)
（T 期）
状態変数であるkTは前の期に決まっている．
今決めることは，ucTを最大にするように，消費cTと残す資 本kT +1を決定すること．
問題は，
cmaxT,kT +1u(cT)
s.t. kT +1−kT = f (kT) − cT −δkT kT :given
kT +1≥0.
制約式を代入すれば，問題は次のように書くことができる． maxkT +1 u
(f (kT) + (1 − δ)kT −kT +1
) s.t.kT :given
kT +1 ≥0.
問題の解，つまり最適な次期資本k∗
T +1はkTの関数．
k∗T +1= φT(kT).
これを最適政策関数，またはpolicy functionと呼ぶ．
policy functionの導出
T 期以降の最大化の必要条件， u′(cT) = λT λT = µ
kt+1 ≥0, µ ≥ 0, and µkT +1 = 0. より，
u′(cT) = µ µkT +1 = 0.
u′(cT) = µ > 0 であるから，kT +1= φT(kT) = 0． よって，予算制約式より，
cT = f (kT) + (1 − δ)kT −φT(kT)
とpolicy functionはkTの関数であることがわかる．
この政策関数をもとの問題に代入すると，
VT(kT) =u(f (kT) + (1 − δ)kT −φT(kT)
)
とかくことができる．
VT(kT) は，時点 T ，状態 kTであるときに達成される最大の効用を 評価したものであり，「状態評価関数(state evaluation function)」 あるいは「価値関数(value function)」と呼ばれる．
（T − 1 期）
T 期以降については，T − 1 期に決めた kTに基づいて，VT(kT) によって最適化されている．
T 期以降は VT(kT) によって最適化されているとして，T − 1 期 の問題だけを考えれば，以降は全て最適化されている．
cmaxT −1,kT
u(cT −1) + βVT(kT)
s.t.kT −kT −1 = f (kT −1) − cT −1−δkT −1 kT −1:given
制約式を代入してcT −1を消去すると， maxkT
u(f (kT −1) + (1 − δ)kT −1−kT)+ βVT(kT) s.t.kT −1:given
最適な次期資本はkT −1の関数となる． kT∗ = φT −1(kT −1)
この政策関数をもとの問題に代入．value functionは， VT −1(kT −1) =u(φ∗T −1(kT −1))+ βVT(kT) とかくことができる．
VT −1(kT −1) は，時点 T − 1，状態 kT −1であるときに達成される 最大の効用を評価したvalue function．
(一般のt 期）
t + 1 期以降については，t 期に決めた kt+1に基づいて，
Vt+1(kt+1) によって最適化されている．
Vt+1(kt+1) を与えられたものとして，t 期の問題だけを考えれ ば，以降は全て最適化されている．
maxct,kt+1u(ct) + βVt+1(kt+1)
s.t.kt+1−kt = f (kt) − ct −δkt kt :given
制約式を代入してctを消去すると， maxkt+1 u
(f (kt) + (1 − δ)kt−kt+1
)
+ βVt+1(kt+1)
s.t.kt :given 解である最適次期資本k∗
t+1 = φt(kt) をもとの問題に代入 Vt(kt) =u
(f (kt) + (1 − δ)kt−φ∗t(kt)
)
+ βVt+1(kt+1)
(現在t=0)
maxc0,k1
u(c0) + βV1(k1) s.t. k1−k0= f (k0) − c0−δk0
k0 :given
制約式を代入してc0を消去すると， maxk1
u(f (k0) + (1 − δ)k0−k1)+ βV1(k1) s.t.kt :given
解である最適次期資本k∗
1= φ0(k0) もとの問題に代入
V0(k0) =u(f (k0) + (1 − δ)k0−φ∗0(k0)
)
+ βV1(k1)
以上の操作で，各期の最適な次期資本および各期の最適な消費額 が政策関数として表現された．
以下のように各期の最適政策と遷移式に基づいて，逐次に最適な 消費額が決定される．
1 t = 0 において，初期値は k0．期末（次の期）の資本ストック はk∗
1 = φ0(k0).このとき最適な消費は， c∗0= f (k0) + (1 − δ)k0−φ0(k0)．
2 t = 1 において，資本ストックは k1．期末（次の期）の資本ス トックはk∗
2 = φ1(k1).このとき最適な消費は， c∗1= f (k1) + (1 − δ)k1−φ1(k1)．
...
3 t 期において，資本ストックは kt．期末（次の期）の資本ス トックはk∗
t+1 = φt(kt).このとき最適な消費は， c∗t = f (kt) + (1 − δ)kt−φt(kt)．
...
4 T 期において，資本ストックは kT．期末（次の期）の資本ス トックはk∗
T +1 = φT(kT) = 0.このとき最適な消費は， c∗T = f (kT) + (1 − δ)kT −φT(kT)．横断面条件より kT +1= 0
後ろ向き帰納法は，時間が有限であるときならば有効である．し
かし期間T が無限であるようなケースでは，後ろが定まっていな
いために，後ろ向き帰納法を使うことができない．そのため準備 として次のような再帰関係式を考察しておく．
基本的再帰関係式 (fundamental recurrence
relation)
もう一度同じ問題を考えて，問題が再帰的な関係を持つことを考 えてみる．
max
ct,kt+1
∑T t=0
βtu(ct) subject to
kt+1−kt = f (kt) − ct−δkt fort = 1, 2, · · · , T, k0 = k0
kT +1 ≥0.
最後のT 期の問題は， VT(kT) = max
cT,kT +1u(cT)
s.t.kT +1−kT = f (kT) − cT−δkT kT :given, kT +1 ≥0.
この問題は簡単に解くことができ， u′(cT) = λT
λT = µ
kt+1 ≥ 0, µ ≥ 0, andµkT +1= 0.
以上から，
u′(cT) = µ µkT +1= 0.
u′(cT) = µ > 0 であるから，横断性条件 kT +1= φ(kT) = 0. 予算制約式より最適な消費は，
cT = f (kT) + (1 − δ)kT−0
T 期の状態評価関数は，
VT(kT) = u(f (kT) + (1 − δ)kT
). (1)
この最後の評価関数を「境界条件(boundary condition)」と呼 ぶことがある．
次にT − 1 期以降の問題を考察すると， VT −1(kT −1) = max
cT −1,cT,kT,kT +1u(cT −1) + βu(cT) (2)
s.t.kT −kT −1= f (kT −1) − cT −1−δkT −1 kT +1−kT = f (kT) − cT −δkT kT −1:given
kT +1≥ 0. この問題を書き換えると，
VT −1(kT −1) = max cT −1,kT
[u(cT −1) + β max cT,kT +1u(cT)
] s.t.kT −kT −1= f (kT −1) − cT −1−δkT −1
kT +1−kT = f (kT) − cT −δkT kT −1:given.
よって，(1)のVT(kT) を用いると， VT −1(kT −1) = max
kT
{u(f (kT −1) − kT + (1 − δ)kT −1
| {z }
cT −1
)
+ βVT(kT)
} (3)
と書くことができる．
同じくT − 2 期以降の問題は， VT −2(kT −2) = max
cT −2,cT −1,cT,kT −1,kT,kT +1u(cT −2) + βu(cT −1) + β 2u(c
T) (4)
s.t. kT −1−kT −2 = f (kT −2) − cT −2−δkT −2 kT−kT −1= f (kT −1) − cT −1−δkT −1 kT +1−kT = f (kT) − cT −δkT
kT −2:given, kT +1≥ 0.
となる．この問題は次のように書き直すことができる． VT −2(kT −2) = max
cT −2,kT −1
[
u(cT −2) + β{ max
cT −1,cT,kT,kT +1u(cT −1) + βu(cT)
}] s.t.kT −1−kT −2= f (kT −2) − cT −2−δkT −2
kT −kT −1= f (kT −1) − cT −1−δkT −1
kT +1−kT = f (kT) − cT−δkT
kT −2 :given, kT +1≥0.
中括弧における最大化問題は(2)のVT −1(kT −1) に対応するため，最 終的に
VT −2(kT −2) = max
kT −1
{u(f (kT −2) − kT −1+ (1 − δ)kT −2)+ βVT −1(kT −1)} (5)
と書くことができる．
同じくT − 3 期以降の問題は， VT −3(kT −3) = max
cT −3,cT −2,cT −1,cT,kT −2,kT −1,kT,kT +1u(cT −3) + βu(cT −2) + β 2u(c
T −1)
+ β3u(cT) (6) s.t.kT −2−kT −3= f (kT −3) − cT −3−δkT −3
kT −1−kT −2= f (kT −2) − cT −2−δkT −2 kT −kT −1= f (kT −1) − cT −1−δkT −1 kT +1−kT = f (kT) − cT −δkT kT −3:given
kT +1≥ 0. となる．
この問題は次のように書き直すことができる． VT −3(kT −3) = max
cT −3,kT −2
[
u(cT −3) + β
{ max
cT −2,cT −1,cT,kT −1,kT,kT +1u(cT −2) + βu(cT −1) + β 2u(c
T)
}] s.t.kT −2−kT −3= f (kT −3) − cT −3−δkT −3
kT −1−kT −2= f (kT −2) − cT −2−δkT −2
kT −kT −1= f (kT −1) − cT −1−δkT −1 kT +1−kT = f (kT) − cT −δkT kT −3:given
kT +1≥ 0.
中括弧における最大化問題は(4)のVT −2(kT −2) に対応するため，最 終的に
VT −3(kT −3) = max
kT −2
{u(f (kT −3) − kT −2+ (1 − δ)kT −3)+ βVT −2(kT −2)} (7)
と書くことができる．
一般にt 期については， Vt(kt) = max
cτ,kτ+1
∑T τ=t
βτ−tu(cτ)
s.t.kτ+1−kτ= f (kτ) − cτ−δkτ (forτ = t, · · · , T − 1,) kt :given, kT +1 ≥0.
となる．次のように書き直してみると， Vt(kt) = max
ct,kt+1
u(ct) + β maxcτ,kτ+1
∑T τ=t+1
βτ−t−1u(cτ)
s.t.kt+1−kt = f (kt) − ct−δkt
kτ+1−kτ = f (kτ) − cτ−δkτ (forτ = t + 1, · · · , T − 1,) kt :given.
これまでの考えと同様にすれば後ろの括弧はt + 1 期以降の問題で あることがわかる．よって
Vt(kt) = max
kt+1
{u(f (kt) − kt+1+ (1 − δ)kt)+ βVt+1(kt+1)} (8)
と書くことができる．この式はベルマン方程式(Bellman’s equation)と呼ばれる．
以上をまとめると
初期値k0 = k0と境界条件 VT(kT) = u
(f (kT) + (1 − δ)kT) とt = 0, 1, 2, · · · , T − 1 についてのベルマン方程式
Vt(kt) = max kt+1
{u(f (kt) − kt+1+ (1 − δ)kt
)
+ βVt+1(kt+1)
}
により，各期の状態評価関数(value function)が VT(kT) → VT −1(kT −1) → · · · → V0(k0)
のように求まる．policy functionは，状態評価関数を求めた後で， maxkt+1
{u(f (kt) − kt+1+ (1 − δ)kt)+ βVt+1(kt+1)} (fort = 0, 1, 2, · · · , T − 1.)
の解である最適政策関数はktの関数k∗
t+1 = φt(kt),
c∗t = f (kt) − φt(kt)
|{z}
kt+1
+(1 − δ)ktとなる．
最適政策関数 (optimal policy function)
maxkt+1
{u(f (kt) − kt+1+ (1 − δ)kt)+ βVt+1(kt+1)} (fort = 0, 1, 2, · · · , T − 1.)
の解を求める．kt+1で微分して，最大化のための必要条件を求め ると，
−u′(ct) + βVt+1′ (kt+1) = 0 (9)
⇐⇒u′(ct) = βVt+1′ (kt+1) (10)
⇐⇒u′(f (kt) − kt+1+ (1 − δ)kt ) = βVt+1′ (kt+1) (遷移式を代入．) (11)
⇐⇒kt+1∗ = φt(kt) (12) と，最適政策関数はktの関数である.
オイラー方程式の導出
k∗t+1= φt(kt) を用いると，ベルマン方程式は， Vt(kt) = u(f (kt) − φt(kt) + (1 − δ)kt
)
+ βVt+1
(φt(kt)) (fort = 0, 1, 2, · · · , T
のように書くことができる．両辺をktで微分すると， Vt′(kt) = u′(c∗t)[f′(kt) − φ′t(kt) + (1 − δ)]+ βVt+1′ (kt+1)φ′t(kt)
⇐⇒Vt′(kt) = u′(c∗t)[f′(kt) + (1 − δ)]+ φ′t(kt)
[−u′(c∗t) + βVt+1′ (kt+1)]
ここで，最大化のための一階条件(10)式を用いると第二項が消え (これを包絡面の定理(envelope theorem)という)，
⇐⇒Vt′(kt) = u′(ct∗)[f′(kt) + (1 − δ)] が得られる．これと，(10)式より，
u′(ct) = βu′(ct+1)[f′(kt+1) + (1 − δ)]
II 動的計画法 (dynamic programming) ：無限
期間
II.1 ベルマン方程式の導出
中央計画者問題を考察する． maxct,kt+1
∑∞ t=0
βtu(ct)
subject to
kt+1−kt = f (kt) − ct −δkt k0= k0
ここで0 < β < 1 は，割引因子(discount factor)である．効用関数 u(·) と生産関数 f (·) は，
u(0) = 0, u′(·) > 0, u′′(·) < 0, u′(0) = ∞, u′(∞) = 0 f (0) = 0, f′(·) > 0, f′′(·) < 0, f′(0) = ∞, f′(∞) = 0
ここで状態評価関数(value function)は次のように書くことがで きる．
V0(k0) = max ct,kt+1
∑∞ t=0
βtu(ct) (13) s.t.kt+1−kt = f (kt) − ct−δkt
k0 :given
V0(k0) 効用を最大にする消費の経路に基づいて測った効用である
から，間接効用関数(indirect utility function)と対応している．
ベルマンの最適性の原理から，(13)は， V0(k0) = max
c0,k1
{u(c0) + β max
cτ,kτ+1
∑∞ τ=1
βτ−1u(cτ)} (14) s.t.kt+1−kt = f (kt) − ct−δkt, k0:given
と書くことができる．括弧の中の第二項は，t = 1 から先の効用最 大化問題であるから，
V0(k0) = max
c0,k1
{u(c0) + βV1(k1)} (15) s.t.k1−k0 = f (k0) − c0−δk0, k0 :given.
c0を消去すれば，V0(k0) は，次のように書くことができる． V0(k0) = max
k1
{u(f (k0) − k1+ (1 − δ)k0
)
+ βV1(k1)} (16)
一般のt 期では， Vt(kt) = max
cτ,kτ+1
∑∞ τ=t
βτ−tu(cτ) (17) s.t.kτ+1−kτ= f (kτ) − cτ−δkτ, kt :given
と表すことができる．よって同様にして， Vt(kt) = max
ct,kt+1
u(ct) + β maxcτ,kτ+1
∑∞ τ=t+1
βτ−t−1u(cτ)
s.t.kt+1−kt = f (kt) − ct−δkt, kt :given
と書くことができ,ctを消去すれば，Vt(kt) は，次のようにベルマ ン方程式(Bellman equation)として書くことができる．
Vt(kt) = max
kt+1
{u(f (kt) − kt+1+ (1 − δ)kt)+ βVt+1(kt+1)} (18)
さらに，(17)は時間t に関わらず同じ形をしていることから，t に 依存しない時間不変な状態評価関数(time-invariant value function) として表すことができる．つまり，
V(·) = Vt(·).
よって，ベルマン方程式は，時間不変な関数V(·) について V(kt) = max
kt+1
{u(f (kt) − kt+1+ (1 − δ)kt)+ βV(kt+1)}.
II.2 状態評価関数 (value function) とポリシー
関数 (policy function)
次に，得られたベルマン方程式に基づいてvalue functionを求め，
その後policy functionを求める．有限期間の問題と異なり，無限期
間の問題では最後のT 時点が無いため，後ろ向き帰納法を用いて 後ろ向きに解くことができない．変わりに，value functionV(·) が 時間不変であることから，問題は
V(kt) = max
kt+1
{u(f (kt) − kt+1+ (1 − δ)kt)+ βV(kt+1)}. (19)
を満たすような関数V(·) を見つけるという問題になっている．
(i) Value function
関数が解になるような問題であるため，取り扱うのは関数空間の 問題であり，関数解析(functional analysis)の知識が必要不可欠と なる．しかしここでは，value functionV(·) は一意に存在する十分 条件を満たしている．よって以下のvalue function iterationが利用 可能である．
1 関数方程式(19)は，一意で強凹関数である解を持つ．
2 一般的にk
t+1 = ˜k，kt = k と置くとする．有限でかつ連続であ る関数V0を初期値として，次の繰り返し(iteration)によって，
j → ∞ としたときに Vj(·) は関数方程式の解に近づく． Vj+1(k) = max
˜k
{u(f (k) − ˜k + (1 − δ)k)+ βVj(˜k)
} s.t.k : given.
(ii) Policy function
(19)式において，左辺の最大化問題を考える．一階条件はkt+1で 微分して，
−u′(ct) + βV′(kt+1) = 0
⇔u′(ct) = βV′(kt+1) (20)
⇔u′(ct) = βV′( f (kt) − ct+ (1 − δ)kt) (21) である．u(·), f (·),V(·) はどれも時間不変な関数であるため，この 式を解くことで，時間不変なpolicy function (time invariant policy function)：
kt+1 = φ(kt) (22) がt 期の状態 ktの関数として得られる．これはt 期において，状態 ktのときの最適な次期資本を表す関数である．
またt 期において，状態 ktのときの最適な消費ctは，
ct = f (kt) − φ(kt) + (1 − δ)kt (23)
(iii) Euler equation
policy function (23)のct = f (kt) − φ(kt) + (1 − δ)ktを用いると，ベル マン方程式は，
V(kt) = u(f (kt) − φ(kt) + (1 − δ)kt
)
+ βV(kt+1)
のように書くことができる．両辺をktで微分すると， V′(kt) = u′(ct)[f′(kt) − φ′(kt) + (1 − δ)]+ βV′(kt+1)φ′(kt)
⇐⇒V′(kt) = u′(ct+1)[f′(kt) + (1 − δ)]−φ′(kt)
[u′(ct) − βV′(kt+1)]
ここで，最大化のための一階条件(20)式を用いると第二項が消え (これを包絡面の定理(envelope theorem)という)，
V′(kt) = u′(ct)[f′(kt) + (1 − δ)] (24) が得られる．これと，(20)式より，
u′(ct) = βV′(kt+1)
⇐⇒ u′(ct) = βu′(ct+1){f′(kt+1) + (1 − δ)} となり，オイラー方程式を得ることができる．
II.3 動的計画法：例
value functionを求める方法
(i) Value function iteration
(ii) Howard’s improvement algorithm (iii) Guess and verify
(i) Value function iteration
このアルゴリズムは，すでにほとんど解説済み．
1 一般的にk
t+1 = ˜k，kt = k と置くとする．有限でかつ連続であ る関数V0を初期値として与える．
2 次の繰り返し(iteration)を行う． Vj+1(k) = max
˜k
{u(f (k) − ˜k + (1 − δ)k)+ βVj(˜k)
} s.t.k : given.
3 j = j + 1 とおく．
4 V
jが収束するまで，繰り返す．
この手法をvalue function iterationとか，iterating on the Bellman equationと呼ぶ．
(ii) Howard’s improvement algorithm
このアルゴリズムについては，後で一般的なケースについて説明 する．
(iii) Guess and Verify
効用関数u(c) = log(c)，生産関数 f (k) = Akαというケースを考え る．ただし0 < α < 1, A > 0 である．また減耗率 δ = 1 とする．ベ ルマン方程式(19)式は，
V(kt) = max
kt+1
{log(Akαt −kt+1)+ βV(kt+1)} (25)
である．このベルマン方程式を満たすようなV(·) の関数を見つけ たい．今，関数V(·) を
V(kt) = E + F log(kt) (26)
と推測(guess)する．E と F はまだ決まっていない係数
(undetermined coefficients)である．
このguessに基づいて，一階条件からpolicy functionを導出してみ よう．(25)式左辺の最大化の一階条件は，
− 1 ct
+ βV′(kt+1) = 0
⇔ 1 ct = βV
′(kt+1) (27)
⇔ − 1 ct + βF
1 kt+1 = 0
⇔ 1 ct = βF
1 Akαt −ct
⇔ct = Ak
α t −ct
βF
⇔ (
1 + 1 βF
)
ct = Ak
α t
βF
⇔ct = Ak
α t
1 + βF.
またkt+1のpolicy functionは，
kt+1 = Akα−ct
⇔kt+1 = Akα− Ak
α t
1 + βF
⇔kt+1 = Akα− Ak
α t
1 + βF
⇔kt+1 = βF 1 + βFAk
α t
となる．(24)より，
V′(kt) = βV′(kt+1)αAkα−1t
⇔V′(kt) = 1 ctαAk
α−1
t ((27)式より)
⇔V′(kt) = Ak
α−1 t Akαt 1+βF
(ctのpolicy functionより)
⇔V′(kt) = (1 + βF)αk−1t (28)
一方，(26)式をk について微分したものは，
V′(kt) = Fkt−1 (29) (28)と(29)とを比較すると，
F = (1 + βF)α
⇔F = α 1 − αβ
であることがわかる．よって，value functionおよびpolicy functionは，
V(kt) = E + α
1 − αβlog(kt) (30) ct = (1 − αβ)Aktα (31)
kt+1 = Aαβkαt (32)
k
tのダイナミクス
t 期に状態 ktのとき，最適なkt+1はpolicy functionkt+1 = Aαβkαt に よって決まる．つまり最適経路はkt+1 = Aαβktαという差分方程式 を満たしていることになる．対数をとると，
log kt+1 = log(Aαβ) + α log kt (33)
|α| < 1 より，t → ∞ のとき，ktはある有限な値に収束していく．こ の定常状態は，
k = Aαβkα
⇔k = (Aαβ)1−α1
III 動的計画法：一般的な定式化
関数空間の問題
関数解析(functional analysis)の知識
不確実性のないケース
割引因子として0 < β < 1 を置く．目的は以下のペイオフ関数 r(·, ·) のは割引現在価値を最大にするように，無限期間の操作変数 (control variables){ut}∞t=0を選ぶことである．
max{ut}∞t=0
∑∞ t=0
βtr(xt, ut) (34) s.t. xt+1 = g(xt, ut), x0 :given.
ペイオフ関数r(·, ·) は，凹関数であると仮定．
xt+1= g(xt, ut) は，xtの遷移を表す遷移式(transition equation)． 集合{(xt+1, xt) : xt ≤g(xt, ut)} は，凸集合で，かつコンパクト集 合であるとする．
目的：時間不変(time-invariant)なポリシー関数(policy function)h を見つける．h は，状態変数(state variables)xtから操作変数 (control variables)utへのmappingであり，
ut = h(xt) (35) xt+1= g(xt, ut) (36) x0:given,
に基づいて作られた系列{ut}∞
t=0は元の問題の解なる．このような 解の形式を”recursive”と呼ぶ．
状態評価関数(value function)は， V0(x0) = max
{ut}∞t=0
∑∞ t=0
βtr(xt, ut) (37) s.t. xt+1 = g(xt, ut), x0:given.
このvalue functionは次のように書くことができる．
V0(x0) = max
u0
{r(x0, u0) + β max
{uτ}∞τ=1
∑∞ τ=1
βτ−1r(xτ, uτ)} s.t. xt+1= g(xt, ut), x0 :given. 第二項に(37)を利用すると，
V0(x0) = max
u0
{r(x0, u0) + βV1(x1)}
s.t. xt+1 = g(xt, ut), x0:given.
一般のt 期についても同様にして，ベルマン方程式を導出できる． Vt(xt) = max
ut
{r(xt, ut) + βVt+1(xt+1)} s.t. xt+1 = g(xt, ut), xt :given. ここで，(37)はt に関係しない定式化になっているため，
V0(·) = V(·) と時間不変(time-invariant)な関数として書くことがで きる．よって，一般に˜x = xt+1，x = xt，u = utとするとき，V(·) は
V(x) = max
u
{r(x, u) + βV( ˜x)} (38) s.t. ˜x = g(x, u), x :given,
というベルマン方程式の解になる．
value functionV(·) をどのように見つけるかは，あとに議論すると して，V(·) が見つかれば，policy functionは，
maxu
{r(x, u) + βV( ˜x)} s.t. ˜x = g(x, u)
x :given. の解として求めることができる．
まとめると，問題は次のようになる．
次のベルマン方程式の解としてvalue functionV(·)，policy function h(·) を求める．
V(x) = max
u
{r(x, u) + βV( ˜x)} (39) s.t. ˜x = g(x, u), x :given,
policy functionh(x) と ˜x = g(x, u) を代入すれば，定義域上の任意の x に対して
V(x) = r(x, h(x)) + βV(g(x, h(x))). (40)
未知の関数であるV(·)，h(·) を解とする関数方程式(functional equation)が得られる．
以上の仮定の下で，次のことがわかる．
1. 関数方程式(39)は，一意で強凹関数である解を持つ．
2. 有限でかつ連続である関数V0を初期値として，次の繰り返し (iteration)によって，j → ∞ としたときに Vj(·) は関数方程式の解 に近づく．
Vj+1(x) = max
˜x
{r(x, u) + βVj( ˜x)
} s.t. x : given.
3. (39)の右辺を最大にする必要条件は，
∂r(x, u)
∂u + βV
′(g(x, u))∂g(x, u)
∂u = 0 (41) この必要条件を満たす，一意で時間不変(time-invariant)なpolicy functionh(·) が存在する．
