ダイナミック・プログラミング(動的計画法、DP)を直感的に理解する

この記事では、確率制御問題の解法アルゴリズムであるダイナミック・プログラミング(動的計画法、DP)について述べる。

確率制御問題は、ファイナンスにおける消費・ポートフォリオ選択問題(マートンのポートフォリオ問題)や強化学習に現れる最適化問題である。

この記事では直感的な理解を目指すため、数学的厳密性にはこだわらない。

本記事の内容は下記書籍の内容を参考にしているため、合わせて参照してほしい。

目次


期待効用最大化問題

投資家が消費\( c_t\)を制御(決定)することで、期待効用を最大化する問題を考える。

すなわち、効用関数を\( U\left(c_t, x_t\right)\)として
\[
\underset{{c}}{\max}E_t\left[\int_{t}^{T}U\left(c_s, x_s\right)ds\right]
\]という問題を考える。

ここで\( x_t\)は状態変数であり、
\[
dx=a(x, c)dt+b(x, c)dz
\]を制約条件とする。\( dz\)は標準ブラウン運動である。

この期待効用最大化問題は、数学的には確率制御問題と呼ばれる最適化問題の一種である。

間接効用関数(価値関数)

消費\( c_t\)を最適に制御(決定)するという条件をつけたときの期待効用関数を、間接効用関数(Indirect utility function)とか、価値関数(Value function)と呼ぶ。

間接効用関数は状態変数と時点の関数として表せるので、これを\( J(x_t,t)\)と書くことにすると、
\[ \begin{split}
J(x_t,t)&=\underset{{c}}{\max}E_t\left[\int_{t}^{T}U\left(c_s, x_s\right)ds\right]\\
&=\underset{{c}}{\max}E_t\left[\int_{t}^{t+\Delta t}U\left(c_s, x_s\right)ds+\int_{t+\Delta t}^TU\left(c_s, x_s\right)ds\right]
\end{split} \]と表せる。


ベルマンの最適性の原理

間接効用関数を考察するため、以下の命題を認める。

Bellman's Principle of Optimality,最適性の原理
「将来のある時点の状態変数の実現値を所与とすれば、その時点以降の決定は、当該状態変数の実現値に対して最適に行われる。」

この命題を噛み砕いて言えば、

「消費\( c_t\)を最初から最適に制御するならば、途中時点以後の決定もまた、最適になる。」

ということである。

最適に制御した消費を「最適政策(Optimal policy)」と呼ぶことにすると、この命題は、

「最適政策は、最初の状態および最初の決定が何であっても、残りの決定列は最初の決定から生じた状態に関して最適政策を構成するという性質をもつ」

「最適政策は最適部分政策だけから成る」

などと言い換えることが出来る。

ハミルトン-ヤコビ-ベルマン方程式(確率的連続時間ベルマン方程式)

最適性の原理を用いれば、間接効用関数\( J(x_t,t)\)は次のように書き換えられる.
\[
\begin{split}
J(x_t,t)&=\underset{c}{\max}E_t\left[\int_{t}^{t+\Delta t}U\left(c_s, x_s\right)ds+\underset{c}{\max}E_{t+\Delta t}\left[\int_{t+\Delta t}^{T}U\left(c_s, x_s\right)ds\right]\right]\\
&=\underset{c}{\max}E_t\left[\int_{t}^{t+\Delta t}U\left(c_s, x_s\right)ds+J(x_{t+\Delta t}, {t+\Delta t})\right]\\
\end{split}
\]
二次までの近似計算により,
\[
\begin{split}
J(x_t,t)=&\underset{c}{\max}E_t\left[U(c_t, x_t)\Delta t+J(x_t, t)+J_x\Delta x+J_t\Delta t\right.\\
&\left.+\frac{1}{2}J_{xx}(\Delta x)^2+J_{xt}\Delta x\Delta t+\frac{1}{2}J_{tt}(\Delta t)^2+o(\Delta t)\right]\\
\end{split}
\]
を得る。ただし下付き文字は偏微分する際の変数を示す。

ここで\( \Delta x\approx a(x, c)\Delta t+b(x, c)\Delta z+o(\Delta t)\)であり、\( \Delta z=\sqrt{\Delta t}\tilde{\epsilon}\)、\( \tilde{\epsilon}\sim N(0,1)\)である。


両辺から\( J(x_t,t)\)を引いて,\( \Delta J=\left[J_t+J_xa+\frac{1}{2}J_xxb^2\right]\Delta t+J_xb\Delta z\)とおけば
\[
\begin{split}
0=&\underset{c}{\max}E_t\left[U(c_t, x_t)\Delta t+\Delta J+o(\Delta t)\right]\\
\end{split}
\]となる。

\( E_t\left[J_xb\Delta z\right]\)の項が\( 0\)に等しいことに注意して、両辺を\( \Delta t\)で除して\( \Delta t\rightarrow0\)の極限を取ると、
\[
\begin{split}
0=&\underset{c}{\max}E_t\left[U(c_t, x_t)+J_t+J_xa+\frac{1}{2}J_xxb^2\right]\\
\end{split}
\]という偏微分方程式を得る。

この偏微分方程式をハミルトン-ヤコビ-ベルマン方程式(HJB方程式)確率的連続時間ベルマン方程式と呼ぶ。

HJB方程式は、ディンキン・オペレータ(無限小生成作用素)\( L[\cdot]\)を用いて
\[
\begin{split}
0=&\underset{c}{\max}E_t\left[U(c_t, x_t)+L[J]\right]\\
\end{split}
\]とも書ける。

参考文献