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

主に、強化学習

情報系の大学2年生が確率に関連したことを多めに書いてるブログ

Small Grid World のアルゴリズムについて

はじめに

最近、私と友達のnumbくんでNg. Andrew氏の著書である「Reinforcement Learning :An Introduction」(洋書の方)を読んでます。
その著書に書かれているMDP(Markov Decision Process)の一例であるSmall Grid Worldのアルゴリズムについて書いていきたいと思います。
今回は、どちらかというとこの本に書かれてる式やその意味の補足に当たるかと思います。

MDP の定義だけ

まず、Markov Decision Processの定義について書いていきたいと思います。
MDP \equiv  tuple < \cal{S, A,P,R, R} >
 \cal{S} is 有限状態の集合.
 \cal{A}(s) is state  \cal{S}での可能なアクションの集合.
 \cal{P} is 状態遷移確率行列.
 \cal{P^{a}}_{ss'} is  \mathbb{P}  [ S_{t+1} = s' |  S_t = s, A_t = a ]
 \cal{R} is 報酬関数,  \cal{R^{a}}_{s} =  \mathbb{E}  [ R_{t+1}  |  S_t = s, A_t = a ]

Small Grid World

最初から16次元のベクトルで考えるのはハードルが高いので、まず次のような簡単な例から考えていきたいです。
・ ある状態0, 1があったとします。このとき  \cal{S} = \left\{ 0, 1 \right\} と書きます。
・ アクションは「状態 0 に移動する」と「状態 1に移動する」の2つで定義される。このとき \cal{A} = \left\{ 0, 1 \right\} と書きます。
・ 方針(Policy)  \pi (a | s )  \pi (a | s ) = \mathbb{P} \left[ A_{t} = a | S_t = s \right] : 時刻 \cal{t}にアクション  \cal{a}を行う確率.

例えば、時刻 \cal{t}に状態1にいるとき、「状態0に移動する」というアクションを行う確率は  \pi (1 | 0 ) となります。

・上記した  \cal{P^{a}}_{ss'} \cal{P^{0}}_{00} = 1 が何を意味するか考えてみましょう。

時刻tにおいて状態0 にいるとき、「状態0 に移動する」というアクションを行ったら、
時刻(t+1)において状態0にいる確率は1である、という意味になります。

・同様に  \cal{P^{1}}_{10} = 0 は、

時刻t において状態1にいるとき「状態1に移動する」というアクションを行ったら、
時刻(t+1)に状態0にいる確率は0である、という意味になります。

 \cal{R^{a}}_{s}  = \mathbb{E}  [ R_{t+1}  |  S_t = s, A_t = a] は、

時刻tにおいて状態sにいるときに、アクションaを行ったとき、
得られる即時報酬の期待値、という意味になります。

これらのことをもとに評価値の計算をします。

 \hspace{15pt} \displaystyle \cal{v_{k+1}}(s) \, = \, \sum_{a \in \cal{A} }  \pi (a | s ) ( \cal{R^{a}}_{s} + \gamma \sum_{s' \in S} \cal{P^{a}}_{ss'}  \cal{v_{k}}(s')  )

<続きあります.>

参考

www.amazon.co.jp

`