講義ノート４：動的計画法
稲葉 大
First draft 2008 年 10 月 27 日
Revised 2009 年 1 月 7 日
Revised 2010 年 5 月 26 日
目 次
I 動的計画法 (dynamic programming):有限期間 2
I.1 後ろ向き帰納法(backward induction method) . . . 2
I.2 基本的再帰関係式(fundamental recurrence relation) . . . 5
II 動的計画法 (dynamic programming)：無限期間 11 II.1 ベルマン方程式の導出 . . . 11
II.2 状態評価関数 (value function) とポリシー関数 (policy function) . . . 12
(i) Value function . . . 13
(ii) Policy function . . . 13
(iii) Euler equation . . . 13
II.3 動的計画法：例 . . . 14
(i) Value function iteration . . . 14
(ii) Howard’s improvement algorithm . . . 15
(iii) Guess and Verify . . . 15
III 動的計画法：一般的な定式化 18 III.1 不確実性のないケース . . . 18
(i) (42) 式の導出 (Benveniste and Scheinkman (1979)) . . . 21
III.2 ３つの導出方法 . . . 22
(i) Value function iteration . . . 22
(ii) Howard’s improvement algorithm . . . 22
(iii) Guess and verify . . . 23
今回の講義では動的計画法(dynamic programming) を用いた方法を紹介する．ここで紹介す るベーシックな最適成長モデルにおいては，直接の方法でも動的計画法でもどちらの方法を用い
ても良い．しかし実際には，モデルの性質によって異なり，動的計画法しか利用できないケース
（例えばサーチモデル，離散選択のモデルなど）のための準備として動的計画法を学んでおく必 要がある．以下では不確実性のないケースを紹介する．不確実性のあるケースについては，後に 考察していく．並行してAdda and Cooper (2003) の chapter 2，および Ljungqvist and Sargent (2004) の chapter 2 と appendix on functional analysis を読んでおくことを進める．
I 動的計画法 (dynamic programming): 有限期間
以下では動的計画法について直観的な解説をする
1
．次のように記述される中央計画者問題を 考察する．
(SP) max
ct,kt+1
∑T t=0
βtu(ct) subject to
kt+1− kt= f (kt) − ct− δkt for t = 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) な構造を利用して解いていくのが動的計画法である．動的計画法は，以下の原理に基づいて考 察する．
ベルマンの最適性の原理(Bellman’s principle of optimality)
最適政策とは，最初の状態や決定がどうであっても，それ以後の決定が最初の決定によっ て生じた状態に関して最適政策となるように構成しなければならないという性質を持って いる．(西村 (1994)P150 より抜粋)
この考え方を用いると，時間が有限であるときには，後ろ向き帰納法(backward induction method) によって，得られる政策が最適政策になる．なぜなら，後ろ向き帰納法 (backward in- duction method) で求めた解は，ある t 時点を考えるとき，それ以降の政策は常に最適になって いるからである．
I.1 後ろ向き帰納法 (backward induction method)
（T 期）
いま経済はT 期にいるとする．このとき，決定する問題は非常にシンプルである．T 期におい
1
以下の記述も多くを西村(1990) に寄っている．
て，状態変数であるkT は前の期に決まっている値となっている．今決めることは，T 期以降に できることで，効用を最大化することである．つまりucT を最大にするように，今の消費cT と 残す資本kT +1を決定する．よって問題は，
cTmax,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.
この問題の解つまり，最適な次期資本kT +1∗ はkT の関数になっている．これをk∗T +1 = φT(kT) とする
2
．最適に選んだ政策関数(policy function) と呼ぶことがある．この政策関数をもとの問 題に代入すると，
VT(kT) =u(f(kT) + (1 − δ)kT − φT(kT))
とかくことができる．VT(kT) は，時点 T ，状態 kT であるときに達成される最大の効用を評価し たものであり，「状態評価関数(state evaluation function)」あるいは「価値関数 (value function)」 と呼ばれる．
（T − 1 期）
T − 1 期において，問題は次のようになる．T 期以降については，T − 1 期に決めた kT に基づ
いて，VT(kT) によって最適化されている．よって，T 期以降は VT(kT) によって最適化されてい るとして，T − 1 期の問題だけを考えれば，以降は全て最適化されている．
cT −1max,kTu(cT−1) + βVT(kT)
s.t. kT − kT−1 = f (kT−1) − cT−1− δkT−1
kT−1 : given
2
これは次のように導出できる．上の問題のT 期以降の最大化の必要条件は，kT +1で微分して，
u′(cT) = µ
kt+1≥0, µ ≥ 0, and µkT +1= 0.
µ はクーン・タッカー条件に関するラグランジアンである．u′(cT) = µ > 0 であるから，kT +1= φT(kT) = 0 とわ かる．よって，予算制約式より，最適な消費は，
cT = f (kT) + (1 − δ)kT−φT(kT)
であることがわかる．
制約式を代入してcT−1を消去すると， maxkT u
(
f(kT−1) + (1 − δ)kT−1− kT
)
+ βVT(kT) s.t. kT−1 : given
解である最適な次期資本ストックをkT∗ = φT−1(kT−1) とする．この政策関数をもとの問題に代 入すると，
VT−1(kT−1) =u(f(kT−1) + (1 − δ)kT−1− φ∗T−1(kT−1))+ βVT(kT) とかくことができる．
(一般の t 期）
同様にして，t 期において，問題は次のようになる．t+ 1 期以降については，t 期に決めた kt+1
に基づいて，Vt+1(kt+1) によって最適化されている．よって，Vt+1(kt+1) を与えられたものとし て，t 期の問題だけを考えれば，以降は全て最適化されている．
cmaxt,kt+1
u(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
解である最適な次期資本ストックをk1∗ = φ0(k0) とする．この政策関数をもとの問題に代入す ると，
V0(k0) =u(f(k0) + (1 − δ)k0− φ∗0(k0))+ βV1(k1)
とかくことができる．
以上の操作で，各期の最適な次期資本および今期消費額が政策関数として表現された．以下 のように各期の最適政策と遷移式に基づいて，逐次に最適な消費額が決定される．
t = 0 において，初期値は k0．期末（次の期）の資本ストックはk∗1 = φ0(k0). このとき最 適な消費は，c∗0 = f (k0) + (1 − δ)k0− φ0(k0)．
t = 1 において，資本ストックは k1．期末（次の期）の資本ストックはk2∗ = φ1(k1). この とき最適な消費は，c∗1 = f (k1) + (1 − δ)k1 − φ1(k1)．
...
t 期において，資本ストックは kt．期末（次の期）の資本ストックはkt+1∗ = φt(kt). このと き最適な消費は，c∗t = f (kt) + (1 − δ)kt− φt(kt)．
...
T 期において，資本ストックは kT．期末（次の期）の資本ストックはkT +1∗ = φT(kT) = 0. このとき最適な消費は，c∗T = f (kT) + (1 − δ)kT − φT(kT)．
後ろ向き帰納法は，時間が有限であるときならば有効である．しかし期間T が無限であるよ うなケースでは，後ろが定まっていないために，後ろ向き帰納法を使うことができない．その ため準備として次のような再帰関係式を考察しておく．（後ろ向き帰納法ここまで）
—————————————
I.2 基本的再帰関係式 (fundamental recurrence relation)
もう一度同じ問題を考えて，問題が再帰的な関係を持つことを考えてみる． (SP) max
ct,kt+1
∑T t=0
βtu(ct) subject to
kt+1− kt= f (kt) − ct− δkt for t = 1, 2, · · · , T, k0 = k0
kT +1 ≥ 0.
最後のT 期の問題は，
VT(kT) = max
cT,kT +1
u(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 = 0 とわかる．よって，予算制 約式より最適な消費は，
cT = f (kT) + (1 − δ)kT
よって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
)
+ βVT(kT) }
(3)
と書くことができる．
同じくT − 2 期以降の問題は，
VT−2(kT−2) = max
cT −2,cT −1,cT,kT −1,kT,kT +1
u(cT−2) + βu(cT−1) + β2u(cT) (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 +1
u(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(cT−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(cT)]} 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) + β max
cτ,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
)
とベルマン方程式 Vt(kt) = max
kt+1
[
u(f(kt) − kt+1+ (1 − δ)kt
)+ βVt+1(kt+1) ]
(for t = 0, 1, 2, · · · , T − 1.)
により，各期の状態評価関数(value function) が
VT(kT) → VT−1(kT−1) → · · · → V0(k0)
のように求まる．一方，最適政策関数は，状態評価関数を求めた後で， maxkt+1
[
u(f(kt) − kt+1+ (1 − δ)kt
)
+ βVt+1(kt+1) ]
(for t = 0, 1, 2, · · · , T − 1.)
の解として，kt+1∗ = φt(kt), c∗t = f (kt) − φt(kt)
| {z }
kt+1
+(1 − δ)ktと求めることができる．
最適政策関数は次のように求めれば良い． maxkt+1
[
u(f(kt) − kt+1+ (1 − δ)kt
)
+ βVt+1(kt+1) ]
(for t = 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)
⇐⇒k∗t+1= φt(kt) (12)
と，最適政策関数はktの関数であることが確認できた．ct, kt+1の最適経路の扱いは４ページ とおなじである．
オイラー方程式の導出
また，k∗t+1= φt(kt) を用いると，ベルマン方程式は， Vt(kt) = u(f(kt) − φt(kt) + (1 − δ)kt
)+ βVt+1
(
φt(kt)) (for t = 0, 1, 2, · · · , T − 1.)
のように書くことができる．両辺をktで微分すると，
Vt′(kt) = u′(c∗t)[f′(kt) − φ′t(kt) + (1 − δ)]+ βVt+1′ (kt+1)φ′t(kt)
⇐⇒Vt′(kt) = u′(ct∗)[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) ：無限期間
次に無限期間のケースについて，動的計画法を適用することを考えてみる．今までと同様に 最適成長モデルを例として取り上げる．一般の動的計画法の問題については，後にまとめる予 定だが，Ljungqvist and Sargent (2004) などを参照すると良い．
II.1 ベルマン方程式の導出
次のように記述される中央計画者問題を考察する． (SP) max
ct,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) + β max
cτ,kτ +1
[ T
∑
τ =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 function V (·) が時間不変であ ることから，問題は
V(kt) = max
kt+1
[
u(f(kt) − kt+1+ (1 − δ)kt
)+ βV (kt+1) ]
. (19)
を満たすような関数V(·) を見つけるという問題になっている．
(i) Value function
関数が解になるような問題であるため，取り扱うのは関数空間の問題であり，関数解析(func- tional analysis) の知識が必要不可欠となる．しかしここでは，value function V (·) は一意に存 在する十分条件を満たしている．よって以下のvalue function iteration が利用可能である．
1. 関数方程式 (19) は，一意で強凹関数である解を持つ．
2. 一般的に kt+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′(f(kt) − kt+1+ (1 − δ)kt
)= βV′(kt+1) (21)
である
3
．u(·), f (·), V (·) はどれも時間不変な関数であるため，この式を解くことで，時間不変 なpolicy function (time invariant policy function)：
kt+1= φ(kt) (22)
がt 期の状態 ktの関数として得られる．これはt 期において，状態 ktのときの最適な次期資本 ストックを表す政策関数である．
またt 期において，状態 ktのときのt 期の最適な消費 ctは，
ct = f (kt) − φ(kt) + (1 − δ)kt (23) となる．
(iii) Euler equation
policy function (22) の kt+1 = φ(kt) を用いると，ベルマン方程式は， V(kt) = u(f(kt) − φ(kt) + (1 − δ)kt
)
+ βV(φ(kt))
3
計算の過程でct= f (kt) − kt+1+ (1 − δ)ktの関係を利用している．
のように書くことができる．両辺を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+1)[f′(kt) + (1 − δ)] (24)
が得られる．これと，(20) 式より，
u′(ct) = βu′(ct+1)[f′(kt+1) + (1 − δ)]
となり，オイラー方程式を得ることができる．
II.3 動的計画法：例
ここでは効用関数，生産関数を具体的に特定化した例を用いて，動的計画法を適用し，value function を求めてみる．value function を求める方法として代表的なものが 3 つある．
1. Value function iteration
2. Howard’s improvement algorithm 3. Guess and verify
Value function iteration は，先にみた関数方程式の性質を利用したものであり，解を解析的に求め ることができないケースにおいても数値計算によって対応することが可能である．またHoward’s improvement algorithm は，value function iteration ではなく，policy function iteration になっ ているところがポイントである．ここでは，Guess and Verify のみを紹介する．value function iteration および Howard’s improvement algorithm については，ここではアルゴリズムだけを簡 単に説明する．具体的な数値計算の方法については，Adda and Cooper (2003) および Ljungqvist and Sargent (2004) を参照すること．一方，解を解析的に求めることができるケースでは，Guess and Verify という手続きによって，解関数を推測して，それが解になっていることを証明する ことで，解を求める．ただしこの手法が使えるのは，非常に限定的なケースだけであり，より 強力なのは数値計算に基づいた手法である．
(i) Value function iteration
このアルゴリズムは，すでにほとんど解説済みである．
1. 一般的に kt+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. Vjが収束するまで，繰り返す．
この手法をvalue function iteration とか，iterating on the Bellman equation と呼ぶ．
(ii) Howard’s improvement algorithm
このアルゴリズムについては，後で一般的なケースについて説明する．
(iii) Guess and Verify
ここでSargent (1987) の第一章に基づいて，効用関数 u(c) = log(c)，生産関数 f (k) = Akαと いうケースを考える．ただし0 < α < 1, A > 0 である．また減耗率 δ = 1 とする．ベルマン方 程式(19) 式は，
V(kt) = max
kt+1
[
log(Aktα− 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α−1t ((27) 式より)
⇔ V′(kt) = Ak
α−1 t Aktα 1+βF
(ctのpolicy function より)
⇔ V′(kt) = (1 + βF )αk−1t (28) と書くことができる．一方，(26) 式を k について微分したものは，
V′(kt) = F k−1t (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)
E を求めるには，(25) に，上の 3 本を代入して， V(kt) = max
kt+1
[
log(Aktα− kt+1
)+ βV (kt+1) ]
⇔ E + α
1 − αβ log(kt) = log
((1 − αβ)Aktα)+ β [
E+ α 1 − αβ log
(
Aαβktα)]
⇔ E + α
1 − αβ log(kt) = log
((1 − αβ)A)+ α log(kt) + βE + αβ 1 − αβ log
(Aαβ)+ α
2β
1 − αβ log(kt)
⇔ E + α
1 − αβ log(kt) = log
((1 − αβ)A)+ βE + αβ 1 − αβlog
(Aαβ)+ (
α+ α
2β 1 − αβ
)
log(kt)
⇔ (1 − β)E + α
1 − αβ log(kt) = log
((1 − αβ)A)+ αβ 1 − αβ log
(Aαβ)+ ( α
1 − αβ )
log(kt)
log(kt) の係数はまったく同じだから，両辺が等しくなるためには，定数項の部分が等しくなる 必要がある．つまり
(1 − β)E = log((1 − αβ)A)+ αβ 1 − αβ log
(Aαβ)
⇔ E = (1 − β)−1{log((1 − αβ)A)+ αβ 1 − αβ log
(Aαβ)}.
実はこの例では，value function iteration を用いても同じ解を得ることができる．これについ ては，練習問題としておく．
少しktのダイナミクスについて考えてみよう．t 期に状態 ktのとき，最適なkt+1はpolicy functionkt+1 = Aαβktαによって決まる．つまり最適経路はkt+1 = Aαβktαという差分方程式を 満たしていることになる．対数をとると，
log kt+1= log(Aαβ) + α log kt (33)
|α| < 1 より，t → ∞ のとき，ktはある有限な値に収束していく．この定常状態は， k = Aαβkα
⇔ k = (Aαβ)1−α1
III 動的計画法：一般的な定式化
いままでは，最適成長モデルに基づいて動的計画法を説明してきた．そこでの直観的な理 解を生かし，以下ではより一般的な定式化を行う．ベルマン方程式から，状態評価関数(value function) とポリシー関数 (policy function) を導くという手続きはまったく同じである．動的計 画法は，関数が解になるような問題であるため，取り扱うのは関数空間の問題であり，関数解 析(functional analysis) の知識が必要不可欠となる．しかし，数学的に厳密に取扱うにはこの講 義の時間を超えるため，Ljungqvist and Sargent (2004) および Adda and Cooper (2003) に基づ いて直観的な説明だけを行うことにする．数学的には正しくないが直観的に言えば，関数空間 をあたかも実数の空間であるかのように取り合っていると考えるとわかりやすいかもしれない．
III.1 不確実性のないケース
いままで考察してきたモデルは全て不確実性のない(no uncertainty，または deterministic) モ デルであった．以下では不確実性のないケースの一般的な定式化を行う．不確実性のあるケー スは別の講義ノートで改めて解説を行う．
割引因子として0 < β < 1 を置く．目的は以下のペイオフ関数 r(·, ·) のは割引現在価値を最 大にするように，無限期間の操作変数(control variables){ut}∞t=0を選ぶことである．
{umaxt}∞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)} は，凸集合で，かつ コ ン パ ク ト 集 合 で あ る と す る
4
．動 的 計 画 法 で は ，時 間 不 変(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”と呼 ぶ．policy function を見つけるためには，次のような状態評価関数 (value function) を考える必 要がある．これはある状態のときの問題の最適な価値を表したものであり，次のように書くこ
4
数学的には正確ではないが，直観的に説明しておく．凸集合とは，集合(集まり) があったときに，その境界 のどこにもクボミがない状態である．ちなみに凸という漢字は凸集合ではない．コンパクト集合とは，有限で閉じ た閉集合を表す．例えば数直線状に閉区間を考えたときには，値が有限であり，かつ境界を含み，中身が詰まって いる区間が閉区間である．
とができる．
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 に関係しない定式化になっているため5，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 function V (·) をどのように見つけるかは，あとに議 論するとして，V(·) が見つかれば，policy function は，
maxu
[
r(x, u) + βV (˜x)] s.t. ˜x= g(x, u)
x: given.
5t をどこから始めても関数の形は同じままである．
の解として求めることができる．
まとめると，問題は次のようになる．
次のベルマン方程式の解としてvalue function V (·)，policy function h(·) を求める． V(x) = max
u
[r(x, u) + βV (˜x)] (39) s.t. ˜x= g(x, u)
x: given,
policy function h(x) と ˜x= g(x, u) を代入すれば，定義域上の任意の x に対して
V(x) = r(x, h(x))+ βV(g(x, h(x))). (40)
未知の関数であるV(·)，h(·) を解とする関数方程式 (functional equation) が得られる． 以上の仮定の下で，次のことがわかる
6
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 function h(·) が存在 する．
4. 端点を除いて，value function は次のように微分可能である．(40) より，
V′(x) = ∂r
(x, h(x))
∂x + β
∂g(x, h(x))
∂x V
′(g(x, h(x))). (42)
この式の導出はBenveniste and Scheinkman による7．特にx˜= g(u) であるとき，∂x∂g = 0 より，
V′(x) = ∂r
(x, h(x))
∂x (43)
である．
6
証明は省略する．詳しくはLjungqvist and Sargent (2004) および Adda and Cooper (2003) に直観的な説明 が書かれている．また数学的に厳密な取扱いは，Stokey and Lucas (1989) にある．
7(42) 式の導出は後述
5. Euler 方程式の導出
˜
x= g(u) であるとき，(41) 式は，
∂r(x, u)
∂u + βV
′(˜x)∂g(u)
∂u = 0 (44)
上の式に(43) を代入すると，
∂r(x, u)
∂u + β
∂r(x, h(˜˜ x))
∂x˜
∂g(u)
∂u = 0. (45)
のようにEuler 方程式を導出できる8．
(i) (42) 式の導出 (Benveniste and Scheinkman (1979)) (40) より，両辺微分して，
V′(x) = ∂r
(x, h(x))
∂x +
∂r(x, h(x))
∂u
∂h(x)
∂x + βV′(g(x, h(x)))
[∂g(x, h(x))
∂x +
∂g(x, h(x))
∂u
∂h(x)
∂x ]
を少し整理すると，
V′(x) = ∂r
(x, h(x))
∂x + βV
′(g(x, h(x))) ∂g
(x, h(x))
∂x +
[∂r(x, h(x))
∂u + βV
′(g(x, h(x))) ∂g
(x, h(x))
∂u
] ∂h(x)
∂x .
(41) 式より，第三項はゼロであるから，包絡面の定理 (envelope theorem) より (42) 式
V′(x) = ∂r
(x, h(x))
∂x + βV
′(g(x, h(x))) ∂g
(x, h(x))
∂x . が導出される．
8
分かりやすく時間の添え字を戻せば，
∂r(xt, ut)
∂ut
+ β∂r(xt+1, h(xt+1) )
∂xt+1
∂g(ut)
∂ut
= 0
∂r(xt, ut)
∂ut + β
∂r(xt+1, ut+1
)
∂xt+1
g′(ut) = 0
ここで，xt= kt，ut= kt+1，r(xt, ut) = u(f(kt) − kt+1+ (1 − δ)kt
)
，g(ut) = kt+1とおけば，
−u′(ct) + βu′(ct+1) [f′(kt+1) + (1 − δ)] = 0 と，最適成長のモデルにおけるオイラー方程式になっていることが確認できる．
III.2 ３つの導出方法
最適成長の例で説明したとおり，value function と policy function を求めるのには 3 つの方法 がある．
1. Value function iteration
2. Howard’s improvement algorithm 3. Guess and verify
Value function iteration は，先にみた関数方程式の性質を利用したものであり，解を解析的に求め ることができないケースにおいても数値計算によって対応することが可能である．またHoward’s improvement algorithm は，value function iteration ではなく，policy function iteration になって いるところがポイントである．value function iteration および Howard’s improvement algorithm については，ここではアルゴリズムだけを簡単に説明する．具体的な数値計算の方法について は，Adda and Cooper (2003) および Ljungqvist and Sargent (2004) を参照すること．
(i) Value function iteration
1. 有限でかつ連続である関数 V0を初期値として与える． 2. 次の繰り返し (iteration) を行う．
Vj+1(x) = max
u
[r(u, x) + βVj(˜x)] s.t. ˜x= g(x, u)
x: given, 3. j = j + 1 とおく．
4. Vjが収束するまで，繰り返す．
この手法をvalue function iteration とか，iterating on the Bellman equation と呼ぶ．
(ii) Howard’s improvement algorithm
Howard’s improvement algorithm は次のステップからなる．
1. はじめに policy function の初期関数として u = h0(x) を選ぶ．value を計算する．
Vhj(x) =
∑∞ t=0
βtr(xt, hj(xt)),
s.t. xt+1= g(xt, hj(xt)), x0 : given.
2. 次の目的関数を最大にする policy function を，u = hj+1(x) とする． maxu =
[r(x, u) + βVhj
(g(x, u))]
3. j = j + 1 とおく．
4. hj(·) が収束するまで，step 1, 2, 3 を繰り返す．
(iii) Guess and verify すでに解説済み．
参考文献
[1] Adda, Jerome and Russell W. Cooper, (2003) “Dynamic Economics: Quantitative Methods and Applications,” MIT Press.
[2] Benveniste, Lawrence, and Jose Scheinkman, (1979) “On the differentiability of the value function in dynamic models on economics,” Econometrica, Vol. 47(3), 727-732.
[3] チャン, A., C., (1995),「現代経済学の数学基礎〈上〉〈下〉」，CAP 出版
[4] Ljungqvist, Lars and Thomas Sargent, (2004), “Recursive Macroeconomic Theory,” 2nd edition, MIT Press.
[5] 西村清彦，(1990)，「経済学のための最適化理論入門」，東京大学出版会．
[6] Sargent, Thomas, (1987) “Dynamic Macroeconomic Theory,” Harvard University Press. [7] Stokey, Nancy, and Robert Lucas, (1989) “Recursive Methods in Economic Dynamics,”
Cambridge, MA: Harvard University Press.
