これで分かる！動的計画法=DPのポイント

ブログ記事[2005/10/10]からの転載

以下はDynamic Programming（動的計画法、略称「DP」）に関するお勉強メモ。あまり整理されていませんが、ご参考ください！

・Value Function（以下「V」）は極めて緩い条件の下でベルマン方程式を満たす。

・ベルマン方程式が有界な解を持てば（ここで言う解自体が「関数」であることに注意。以下、この関数を「U」とおく）それが唯一の有界解でありVに一致する。

・以上の2点から、Vの有界性が言えれば自動的に「ベルマン方程式に唯一の有界解Uが存在しVと一致する」ことが言える。

・Vが有界になるための十分条件としては
1) Reward Function（以下「r」）が有界
2) State Space（以下「S」）とAction Space（以下「A」）がコンパクトでrが連続
などがポピュラー。

・経済学的に興味深いほぼ全ての問題においてVは有界と考えられるので、取り扱いにくい元の動学問題を考える代わりに、扱いが簡単なベルマン方程式を分析すれば済む。

・つまり、Vの性質やVを与えるOptimal Policyの性質を調べる代わりに、（一般性を失うことなく）UやUを与えるOptimal Policy（それはStationaryになる）の性質を調べればよい。

・Uの性質を調べるために使う大変便利なツールがContraction Mapping Theoremである。

・ベルマンオペレーターTがContractionであることはすぐに調べられるので、Contraction Mapping Theoremを使う際の注意点は主に以下のふたつ（前者は収束先、後者は収束する間に関数の性質が失われないことにそれぞれ対応している）。
1) 関数空間がComplete Metric Spaceであること（例えば「厳密な単調関数の集合」はCompleteではないので注意！）
2) Tがある関数空間から自分自身への写像になっていること（これを保証するためには、関数空間の満たす性質に応じていろいろと条件が必要になってくる）

・このテクニックを使って、Uが連続、単調、凹関数になる条件などを導くことができる。

・Optimal Policyの存在やその性質を調べる際にはMaximum Theoremが大活躍する。

・モデルに不確実性を入れると分析がやや複雑になるが、基本は不確実性のないケースと全く同じである（特に、Sが有限または可算無限集合の場合は使う記号が若干増えるだけで本質的には元の分析と全く変わらない）。

・しかしSが非可算無限集合の場合には確率測度を考える必要があり、この測度の扱いがあることによって、解の存在や性質を議論する際に追加的な条件を課す必要が出てくる。

文献ガイド

西村 (1990) やディキシット (1997) など学部上級向けの定評ある最適化理論のテキストにDPの記述はあるが、あまりにも扱っている内容が乏しい。学部向けのテキストは、バックワード・インダクションによって解くことができる有限期の問題を比較的しっかりと説明した後に、「無限期になっても本質的には同じ」と言って片付けてしまう傾向があると思う。初学者は、こういったやや達観した見方に甘やかされずに、無限期ならではの問題の難しさや、いわゆるRecursive Structureについてしっかりと理解する必要があるだろう。

経済学部の院生がDPを学ぶ際に一番よく使っていると思われるテキストがStokey and Lucas (1989) である。不確実性の存在しない場合の分析は4章に収められている。上記のメモで重要性を指摘したContraction Mapping TheoremとThe Maximum Theoremに関しては3章で詳しく説明している。この3・4章を読めばDPの基本はほぼ全て抑えられるだろう。理論を学んだ後で5・6章の応用例を実際に自分の手を動かして解けばかなり力がつくことは間違いない。9章では不確実性を導入した場合の分析がなされているが、上でも指摘したように基本は4章と全く同じである。7・8で9章のための数学的な準備として確率測度とマルコフ過程を説明しているが、あまり分かり易い記述ではないと感じた。

Sundaram (1996) の12章では、Stokey and Lucas(1989)とほぼ同じレベルの厳密さで、しかもより一層分かり易く、不確実性のない場合のDPが語られている。応用例として載っている新古典派成長モデルの解説も非常に丁寧で分かり易い。マクロ経済学やファイナンスの専門家を目指すのでない限り、DPに関してはこの本で得られる程度の理解で十分な気がする。オススメ！

References

ディキシット (1997) 『経済理論における最適化（第二版）』勁草書房
西村清彦 (1990) 『経済学のための最適化理論入門』東京大学出版会
Stokey and Lucas (1989) "Recursive Methods in Economic Dynamics" Harvard University Press
Sundaram (1996) "A First Course in Optimization Theory" Cambridge University Press