最適停止

出典: ORWiki

【さいてきていし (optimal stopping)】

概要

結合分布が既知である確率変数列 $X_1, X_2, \cdots \,$ ,と実数値利得関数列 $y_0, \ y_1(x_1), \,$ $\ y_2(x_1, x_2), \,$ $\cdots, \ y_{\infty}(x_1, x_2,\dots) \,$ に対して, 逐次に確率変数列 $X_1 \,$ , $X_2 \,$ , $\cdots \,$ を観測し, 各 $n \,$ 段階において $X_1=x_1, X_2=x_2, \cdots, X_n=x_n \,$ を観測後に観測を停止して利得 $y_n(x_1, \dots, x_n) \,$ を得るか, 継続して $X_{n+1} \,$ を観測するかを決定を下す.このとき, 期待利得を最大にする(もしくは期待費用を最小化する)停止時刻を求めるのが最適停止問題である.

詳説

　逐次に観測される確率変数列に基づき, 期待利得を最大化したり期待費用を最小化するためにある行動を取る時刻を選ぶ問題を最適停止問題という. 最適停止は次の2つの要素を持つ. (i) 結合分布が既知である確率変数列: $X_1, X_2, \cdots\,$ , (ii) 実数値利得関数列: $y_0, \ y_1(x_1), \ y_2(x_1, x_2), \cdots ,\,$ $\ y_{\infty}(x_1, x_2, \cdots)\,$ . 逐次に確率変数列 $X_1\,$ , $X_2\,$ , $\cdots\,$ を観測し, 最初の $n\,$ 段階において $X_1=x_1,X_2=x_2, \cdots, X_n=x_n\,$ を観測後に観測を停止して利得 $y_n(x_1, \cdots, x_n)\,$ を得るか, 継続して $X_{n+1}\,$ を観測するかの決定を下す. 全く観測しないならば $y_0\,$ , 決して停止しないならば $y_{\infty}(x_1, x_2, \cdots)\,$ の利得を得る.このとき, 利得を最大にするタイミングである停止時刻を求めるのが最適停止問題である.要素の(ii)は, $Y_n=y_n(X_1, \cdots , X_n)\,$ としたとき, (ii') 結合分布が既知である利得を表す確率変数列: $Y_0, \ Y_1, \ Y_2, \ \cdots, \ Y_{\infty},\,$ としてもよい. このとき, $E(Y_N)\,$ を最大にする停止時刻 $N\,$ を求めるのが最適停止問題であるとも記述できる. $Y_N\,$ を利得ではなく何らかの費用や損失と解釈すると, 費用ないし損失を最小にする停止規則(時刻) $N\,$ を求める問題となる.

　より一般的には, 最適停止問題は次の様に記述されている. 確率空間 $(\Omega, {\mathcal F}, P)\,$ が与えられ, ${\mathcal F}_n\,$ を $X_1, \cdots, X_n\,$ によって生成される $\mathcal F\,$ の部分 $\sigma\,$ 集合, ${\mathcal F}_0=\{\Omega, \phi\}, {\mathcal F}\,$ を $\cup {\mathcal F}_n\,$ によって生成される $\sigma\,$ 集合とし, ${\mathcal F}_0 \subset {\mathcal F}_1 \subset \cdots\subset {\mathcal F}_n \subset \cdots\subset {\mathcal F}_{\infty} \subset {\mathcal F}\,$ とする. (i)(ii) にかわり(i') 増加部分 $\sigma\,$ 集合列: ${\mathcal F}_0 \subset {\mathcal F}_1 \subset \cdots \subset {\mathcal F}_{\infty}\subset {\mathcal F}\,$ , (ii") 結合分布が既知な利得を表す確率変数列: $Y_0,Y_1, \cdots, Y_n, \cdots, Y_{\infty}\,$ ,とし, $Y_n\,$ は ${\mathcal F}_n\,$ -可測, $n=0, 1, \cdots, \infty\,$ とする. $\{N=n\}\in {\mathcal F}_n\,$ である非負整数値確率変数 $N\,$ を停止規則と定義する. (この定義は, いつ停止するかの決定は今までの観測のみに基づき, 将来の観測には基づかないと解釈するとわかりやすい.) このとき $E(Y_N)\,$ を最大にする停止規則 $N\,$ を求めるのが最適停止問題である. 一般に全ての最適停止問題を解くことは難しいが, 有限期間問題と単調問題(monotone problem)は解くことができる. 確率変数列 $X_1, X_2, \cdots, X_n, n<\infty\,$ を観測後に必ず停止しなければならないとき, 有限期間問題と呼ぶ.有限期間問題は基本的に後向きの帰納法 (backward induction) によって解かれる. $n\,$ 期では停止しなければならないので, $V_n^{(n)}\,$ を $V_n^{(n)}(x_1, \cdots, x_n)=y_n(x_1, \cdots, x_n)\,$ と定義する. $(n-1)\,$ 期では, ここで停止したときの利得 $y_{n-1}(x_1, \cdots, x_{n-1})\,$ と, 継続して $n\,$ 期で停止したときの期待利得 $\mbox{E} (V_n^{(n)}(x_1, \cdots, x_{n-1}, X_n)|X_1 = x_1, \cdots, X_{n-1}=x_{n-1})\,$ を比較すれば, $(n-1)\,$ 期で停止すべきか継続すべきかが判明する. $V_{n-1}^{(n)}(x_1, \cdots, x_{n-1})\,$ を次のように定義する. $V_{n-1}^{(n)}(x_1, \cdots, x_n) = \max\{y_{n-1}(x_1, \cdots, x_{n-1}), \mbox{E}(V_n^{(n)}(x_1, \cdots, x_{n-1}, X_n)|X_1 = x_1, \cdots, X_{n-1}=x_{n-1})\}.\,$ 同様に $j=n-2, n-3, \cdots, 0\,$ と後ろ向きに $V_j^{(n)}(x_1, \cdots, x_j)\,$ を定義し,

$\begin{array}{ll} V_j^{(n)}(x_1,\cdots, x_j) = & \max\{y_j(x_1,\cdots, x_j), \\ & \quad \mbox{E} (V_{j+1}^{(n)} (x_1,\cdots, x_j, X_{j+1})|X_1=x_1,\cdots, X_j=x_j) \} \end{array}\,$

とする. このように定義された $V_j^{(n)}(x_1, \cdots, x_j)\,$ は, $X_1=x_1, \cdots\,$ , $X_j=x_j\,$ を観測して $j\,$ 期から始めたときの最大期待利得を表し, 上式は最適方程式と呼ばれる. これは動的計画の最適性の原理によって得られる関数再帰方程式に他ならず, DP(ダイナミック $\cdot\,$ プログラミング)方程式とも呼ばれる. $j\,$ 期においては, 停止して得られる利得 $y_j(x_1, \cdots, x_j)\,$ が $j\,$ 期より継続して得られる最大期待利得 $\mbox{E}(V_{j+1}^{(n)}(x_1, \cdots, x_j, X_{j+1})|X_1 = x_1, \cdots, X_j=x_j)\,$ より良ければ停止し, 逆ならば継続するのが良い. それゆえに, 有限期間問題の最適停止規則 $N\,$ は, 初めて $V_j^{(n)}(x_1, \cdots, x_j)=y_j(x_1, \cdots, x_j)\,$ となる $j\,$ で停止することである. 有限期間問題の最大期待利得は, $V_0^{(n)}\,$ となる.

　最適停止問題において, 事象 $A_n=\{Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\,$ , $n=0, 1, 2, \cdots\,$ が $\textstyle A_0 \subset A_1 \subset \cdots \subset;\ {\bigcup}_1^{\infty} A_n=\Omega \,$ (almost surely) を満たしているとき単調問題とよぶ. 単調問題では, ある条件の下で([1]参照) OLA (one-stage look-ahead) 停止規則 $N:=\min\{n\ge 0: Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\,$ が最適停止規則となる. OLA 停止規則とは, もう1期だけ継続してから停止するよりも, 今停止するほうがよいときに停止することを要求する規則である.

　独自のクラスを形成してきたといえる確率最大化最適停止問題に秘書問題がある. 秘書問題は結婚問題とも呼ばれ, 最も基本となる古典的秘書問題は次のように記述される. 1人の秘書を雇いたい. 面接した応募者には同ランクはなくランク付けが可能とする. 1人ずつ面接する毎に, 今までに面接した応募者の相対ランクに基づき採用するか否かを決めなければならず, 一度不採用にした応募者を採用することはできない. $n\,$ 人の応募者があり, $n\,$ 人の面接の順列の一つが実現する確率が $1/n!\,$ のとき, $n\,$ 人中のベストランクを得る確率を最大にする最適停止規則を求めたい. 最適停止規則は, $r^{\ast}-1\,$ 番目までの応募者は全て採用を見送り, それ以降に最初に面接する相対的ベストの応募者を採用しなさい, となり, ここで, $\textstyle r^{\ast}=\min\{i\ge 1:\sum_{j=i}^{n-1}(1/j) \le 1\}\,$ により $r^{\ast}\,$ は与えられる. $n\to \infty\,$ のとき, $r^{\ast}/n \to 1/{\rm e} \approx 0.3678\,$ となる. 大まかに言うと, $n\,$ が十分大きいとき, 36.8%まではパスしてそれ以降に到着する相対的ベストの応募者を採用するのが最適である.