前回の続き。といっても書く気が失せつつあるので一気に準マルコフ決定過程の説明にはいる。

準マルコフ決定過程

準マルコフ決定過程 (semi-Markov decision process; SMDP) とは、簡単に言えば自己遷移における滞在時間 (sojourn time) を考慮したマルコフ決定過程である（文献では semi-Markov process と書いている）。準マルコフ過程はマルコフ再生過程 (Markov renewal process) と呼ばれているらしい（参考: Markov renewal process - Wikipedia）。

SMDP は組 $\langle \mathbf{X}, \mathbf{A}, P, \rho, F \rangle$ で定義される。ここで各要素の定義は以下の通り。

$\mathbf{X}$ : 状態の有限集合（または可算集合）
$\mathbf{A}$ : 行動の有限集合
$P : \mathbf{X} \times \mathbf{A} \times \mathbf{X} \to [0,1]$ : 状態遷移確率
$\rho: \mathbf{X} \times \mathbf{A} \to \mathbb{R}_+$ : 報酬率 (reward rate)
$F: \mathbf{X} \times \mathbf{X} \times \mathbf{A} \times [0,\infty) \to [0,1]$ : 滞在時間の確率分布関数

通常のマルコフ決定過程との違いは「報酬が時間単位で与えられる」こと、および「滞在時間の確率分布を任意に設定することができる」ことである。 $P_{xy}(a) = \Pr(x_{n+1}=y \mid x_n=x, a_n=a)$ は、行動 $a$ を取ったときの状態 $x$ から $y \neq x$ への状態遷移確率であり、基本的には MDP と同じものである。