読者です 読者をやめる 読者になる 読者になる

ubnt-intrepid's blog

書いてあることがブログの内容です

セミマルコフ決定過程の勉強メモ (2)

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

マルコフ決定過程

マルコフ決定過程 (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 と同じものである。

滞在時間の確率分布

SMDP を特徴づけているのが次に示す滞在時間 (sojourn time) の確率分布

{\displaystyle
  F_{xy}(\tau \mid a) = \Pr(t_{n+1} \leq t_n + \tau \mid x_n = x, x_{n+1}=y, a_n = a)
}

であり、これは状態が  x_n=x に行動  a を伴い遷移したあと、  x_{n+1}=y に遷移するまでの滞在時間が  \tau 以下である確率を意味する。

特に  F \tau微分可能であれば、 \tauの条件付き確率密度関数  f_{xy}(\tau \mid a) を用いて

 {\displaystyle F_{xy}(\tau \mid a) = \int_{0}^{\tau} f_{xy}(\tau' \mid a) d\tau'}

と表すことができる。

マルコフ決定過程との関係

上の SMDP は、(連続時間における)マルコフ決定過程の一般化になっている。具体的には、

 {\displaystyle
  F_{xy}(\tau \mid a) = 1 - e^{- k_x \tau}
}

指数分布 (exponential distribution) で表されるとき、準マルコフ決定過程連続時間マルコフ決定過程 (Continuous-time Markov decision process; CTMDP) と呼ばれる。

補足

 t_{n+1} - t_n = \tau_{n+1} と定義し、 (x_n, \tau_n) を(拡大された状態空間における)状態と解釈すれば、状態遷移確率として次のように書くこともできる。

{\displaystyle
  \Pr(x_{n+1}=y, \tau_{n+1} \leq \tau \mid x_n = x, a_n = a) = P_{xy}(a) F_{xy}(\tau \mid a)
}

...飽きたので今日はここまで

http://ls4-www.cs.tu-dortmund.de/download/buchholz/Slides/CTMDP_V1.1.pdf