Blog

最適停止問題と線形相補性問題

公開日：2025-10-24

最適停止問題

最適停止問題と線形相補性問題の関連をCottleのp.10を参考にまとめる．

有限の状態空間$E = {1,2,...,N }$と遷移確率行列$P$を持つマルコフ連鎖を考える．このマルコフ連鎖はいくらでも繰り返すことができる． 各時刻$t \in {0,1,2,...,T }$では，このマルコフ連鎖に従うプロセスを停止するか継続するかを選択することができる． 時刻$t$に停止を選択した場合は，状態$i$の利得$r_{i}$に 割引率$\alpha \in (0, 1)$を考慮した$\alpha^{t}r_{i}$を獲得してゲームは終了する． 継続を選択した場合は，遷移確率行列$P$に従って，次の状態に進む． $r_{i}$を$i \in E$についてベクトル化したものを$r$とする．

時刻$t$における暫定的な利得は$\alpha^{t} r$と計算できる． さらに，この暫定的な利得と遷移確率行列$P$から，時刻$t+1$に おける割引期待利得を計算すると$\alpha P(\alpha^{t} r)$を得る． 問題は，今の状態で停止したときに得られる利得$\alpha^{t} r$と， 継続したときの割引率を考慮した期待利得$\alpha P(\alpha^{t} r)$とのトレードオフを考えて最適停止時刻を決定することである． つまり各時刻$t$において次の意思決定を行うことになる： \begin{align} \mbox{Stop} \quad &\mbox{if} \quad \alpha P(\alpha^{t} r) \leq \alpha^{t} r \\ \mbox{Continue} \quad &\mbox{if} \quad \alpha P(\alpha^{t} r) > \alpha^{t} r \end{align}

不等号に影響を与えない$\alpha^{t}$を無視すると，各時刻では次の比較によって意思決定が行われることになる： \begin{align} 　\max(\alpha Pr, r) \end{align}

ここで$v_{i}$を初期状態$i$からスタートしたときの(十分長い時間を経たときに到達する)定常状態における期待利得とする (この定常分布は，遷移確率行列$P$の構造によって初期状態依存になるため，この定常状態における期待利得もまた初期状態依存となることに注意されたい)．$v_{i}$を$i \in E$についてベクトル化したものを$v$とする．

定常状態と相補性表現

この定常状態において次の方程式が成立する：

\begin{align} v &= \max \left( \alpha P v , r \right) \\ \Leftrightarrow \quad v-r &= \max \left( \alpha P v - r, 0 \right) \end{align}

この方程式は次のように変換できる： \begin{align} v - \alpha P v \geq 0,\quad v - r \geq 0, \quad \mbox{and} \quad \left( v-r \right)^{\mathsf{T}}\left( v-\alpha P v \right) = 0 \end{align}

すなわち$x=v-r$とすれば，定常状態における期待利得$v$を求めることは，次のLCP$(M,q)$を解くことと等価である： \begin{align} \mbox{find.} \quad &u \in \mathbb{R}^{N} \\ \mbox{such that} \quad &0 \leq x \perp Mx + q \geq 0 \\ \mbox{where} \quad &q = \left( I - \alpha P \right)r \\ &M = I - \alpha P \end{align}

ここで，行列$M$はその非対角線上のすべての要素が非正であり，かつ$Me > 0$（$e$は全要素が1のベクトル）という特性を持つ．

$\alpha \in (0, 1)$であるため，停止時刻は早ければ早い方がよい． したがってプロセスが停止すべき状態に到達したときに，そこで停止の判断を見送ることはありえない． そのため，最適停止時刻はプロセスが最初に集合${ i \in E \mid v_{i} - r_{i} =0 }$ に到達した瞬間となる．

参考文献