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

ubnt-intrepid's blog

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

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

Machine Learning

ここ数ヶ月ぐらい調子が悪い状態が続いていてろくに文章も書けないでいたのだが、急に元気が出てきたので冷めないうちにメモ。 早く回復しないかなぁ…

はじめに

マルコフ過程 (Markov process) および マルコフ連鎖 (Markov chain) は基本的な確率過程の一つであり、 その扱いやすさからそこらかしこの理論に応用されている、あまりにも有名な確率過程である。 そのマルコフ過程(正確にはマルコフ連鎖)に対し、行動と(その行動を計画する動機を与える)報酬、またはコストを付与したモデルがマルコフ決定過程 (Markov decision process; MDP) である。 この確率過程は、離散的な状態・行動を取る確率過程の制御を考える上で最も基本的なものであり、強化学習などでの応用が特に有名である。

マルコフ過程は、自身の状態への滞在時間 (sojourn time) の確率分布が指数分布に限られるという制約がある。 しかし、この制約を満たさないような確率過程も幾つか存在する。 例えば、ある車がデパートなどの拠点に駐車してから再び出発するまでの滞在時間は明らかにその車の利用者(主婦など)の個性・生活様式に依存し、ある特定の時間にピークが立つような分布になる場合が多い。 そのような確率過程に対しマルコフ性を適用するのは、直感的にも強引であると言える。

そのような状況を考慮した拡張がマルコフ過程 (semi-Markov process) であり、 準マルコフ過程に行動と報酬を組み合わせたモデルがマルコフ決定過程 (semi-Markov decision process; SMDP) である。

滞在時間分布の考え方によって準マルコフ過程はいくつかのバリエーションが存在するが、今回はその中でも最もかんたんなものである(と個人的には思う) 「(連続時間)マルコフ連鎖に滞在時間分布  p(\tau|s) を付与したもの」を考えていきたい。

内容(予定)

文献:

マルコフ過程、SMDPについては上の文献を参考にする。この分野のまとまった文献は(サーベイ能力の低さも相まって)あまり見つからないので、もう少しわかりやすそうな物があったら切り替えるかも… あと、記法・専門用語のぶれは適当な可能性があるので注意されたい。

ここまで書いて疲れたので今日はここまで。 できれば最後まで気力が持ってくれるといいけど…