今回の記事でまとめること

状態価値関数 $V^\pi(s)$ の実装

前回の要約

前回は、状態価値関数 $V^\pi(s)$ を以下のように定式化しました．式の中身は『状態価値関数は、直近の報酬に1ステップ先の状態価値関数を足したものである．ただし、方策および遷移確率で未来の取りうる値は枝分かれするので、その期待値をとる』という内容になっています．

$$V^\pi (s) = \sum_{a} \pi(s,a) \sum_{s'}P^a_{ss'} [R^a_{ss'} + \gamma V^\pi (s')]$$

ここで、

$\pi(s, a)$ ：は方策と呼ばれ、状態 $s$ のときに各行動 $a$ をとる確率
$P^a_{ss'}$ ：は状態 $s$ で行動 $a$ を取った時に、状態 $s'$ に遷移する確率
$R^a_{ss'}$ ：は状態 $s$ で行動 $a$ を取り、状態 $s'$ に遷移したときに得られる報酬

となります．それぞれの関係をダイアグラムで描くと以下のように表せます．

f:id:shirakonotempura:20190126165021p:plain

Grid World

実装で対象とする問題では、前回Grid Worldとして紹介した5×5グリッドの格子状の世界を考えます．
以下、仮定のおさらいです．

エージェントは、状態（＝どのグリッドにいるか）に関わらず、上下左右にランダムに1マス移動する方策に従って行動を起こします．
遷移確率（[tex:P^a_{ss'}）は確定的とし、選んだアクションに応じて、必ずそのアクションを起こすものとします．
グリッドの外に出ることはできず、外にでる方向に移動しようとした場合、‐1の負の報酬が与えられ、エージェントの位置は変わらない
図中AおよびBに移動した場合、その行動によらず次のステップでA’およびB'にワープする．その際、それぞれ+10および+5の報酬が与えられる．

f:id:shirakonotempura:20190126155117p:plain

f:id:shirakonotempura:20190126160041p:plain

実装

実装自体は、完全に写経なので元の記事を参考にしてください．

前回も触れましたが、今回の問題設定では終了条件がなく永遠にステップが続きます．そこで、割引率 $\gamma$ を使って未来に行くほど報酬を割引いています．今回は、計算コストの関係上11ステップ先（つまり $S_{t+11}$ ）まで考慮して、状態価値の計算を行っています．

結論から言うと、これではかなり不十分で、Suttonの本に載っている状態価値関数とは結構違っています．

結果

以下に11ステップまで考慮して求めた状態価値を示します．

f:id:shirakonotempura:20190130075123p:plain

唯一報酬が得られるグリッドAおよびBの状態価値が大きく、その周辺のグリッドも高い値になっていることが分かります．一方で、外側に出ようとする可能性が高く、報酬が得られる確率も低い下側のグリッドは総じて報酬が低くなっています．

グリッドAからA'にワープする際に得られる報酬が+10であるにも関わらず、Aの状態価値が10より低い理由は、ワープ後のA'の位置では負の報酬を得る確率が高く、その影響を受けているためです．一方、グリッドBの場合は、B'の一は画面中央付近で、負の報酬を得る確率は高くないのでAと異なり、状態価値は報酬の値（+5）より大きくなっています．

比較のため、Suttonの本に載っている状態価値の値を以下に示します．

f:id:shirakonotempura:20190130070338p:plain

出典：Reinforcement Learning：An Introduction

こちらは無限ステップ先まで考慮した（ちゃんと収束した）状態価値になっています（こちらをどうやって求めたんでしょう・・）．先にも言ったように、まだかなり差異が見られます．つまり、十分収束したと言えるほど計算ができていません．11ステップ先、枝分かれとして $4^{11}$ 通り（約400万通り）まで考慮しているので十分かと思っていましたが、11ステップ先では割引率はあまり低減されていなくて $$\gamma^{11} \simeq 0.31$$ と、まだ30%の寄与度を持っています．つまり、もう考慮してもしなくてもほぼと言えるステップはまだ先だということになります．仮に寄与度1%以下にまで落とそうとすると $$ x > \log_{0.9} 0.01$$ より44ステップ先まで考慮する必要があります・・・．その枝分かれ数たるや、遷移確率を確定的なものとしたとしても $$4^{44} = 3.09×10^{26}!!!$$ なんと、1兆×1兆通りを軽く超えてしまいます．これが次元の呪いというやつなんでしょうか・・．なんと、おそろしい．