前回、状態価値関数を定式化し、決まった方策のもとベストな行動を学習することができました．おそらくこのベストな行動を次の方策としていけば、最適な方策が見つかりそうな気がします．

ですが、実装してみると分かりますが、非常に計算時間が遅いです．誇張じゃなく、考慮する未来を3ステップ増やすだけで、お昼ご飯食べてお茶できるくらい時間が増えたりします．

これは私の学習ノートです．詳しく知りたい方は、以下の記事を呼んでください．

再帰処理と反復処理

先に結論から言うと、再帰処理と反復処理では、反復処理が圧倒的に計算時間が短くなります．圧倒的です．

いきなり再帰処理、反復処理と言ってもよくわからないと思いますので順番に見ていきます．

再帰処理

再帰処理は、これまで枝分かれのダイアグラムで説明してきた計算方法です．
図を省略するため、ある行動を選択した後の遷移確率は確定的（確率１でその行動を実施する）とさせてください．

f:id:shirakonotempura:20190131034155p:plain

図中の緑丸を起点（求めたい状態価値関数）だとします．この状態から、取りうる行動に対して枝分かれをしていきます（下に行くほど未来になります）．

今取った行動（黒丸）から次の状態（赤丸）に遷移します．緑丸の状態価値を求めるには、赤丸の状態価値が必要となります．しかし、緑丸と同様、赤丸の状態価値を求めるにはさらに未来の青丸の状態価値が必要となることが分かります．

この計算方法では状態・行動・その次の状態を使って、どんどん未来を掘り進めていく必要があるため、枝分かれ（考慮すべき未来）が指数関数的に増えていきます．そのため計算時間がバカになりません．

反復処理

次に反復処理による計算方法を紹介します．以下に計算のイメージ図を示します．ダイアグラムは再帰処理の場合と異なり、今の状態と次の状態で終わっています．

f:id:shirakonotempura:20190131034212p:plain

先と同様に、緑丸を起点（求めたい状態価値関数）、次の状態を赤丸で示しています．赤丸の状態価値関数には、適当な値（全部０でいいみたいです）を初期値として設定すればよいです．この赤丸の状態価値を使えば、緑丸の状態価値が分かります．当然、初期値が適当なので、求められる状態価値も変な値です．

今起点とした緑丸以外の全ての状態に対しても同様の計算行い値を更新していきます．この操作を図中の紫色の矢印で示しています．ここまでをk=0ステップとします．

k=0ステップで、上層の状態価値が更新されましたので、k=1ステップの下層の状態価値にそれを利用します．これを繰り返すことで、状態価値を適当に決めた0から反復的に更新させていくことができます．
枝分かれが２層しかないので、計算処理が早くなります．枝分かれが指数関数的に増えることに比べれば、反復回数が増えることの影響はわずかなものなので、再帰処理よりも早く収束します．

このアルゴリズムを方策反復評価（Iterative Policy Evaluation）と呼びます．

『その場更新型』バックアップ（In-place ）

上に示した説明では、上層（ $V(s)$ ）と下層（ $V(s')$ ）で2つの配列を持っています．手順としては、上層のスイープを全状態に対して終了してから、下層に代入し、再度上層のスイープというステップになっています．つまり、スイープ中は下層の状態価値は固定です．

より高速化を図った別の方法として、『その場更新（In-place）型』反復処理のアルゴリズムがあります．ｋのアルゴリズムは配列を１つしか使いません．つまりスイープの途中で、ある状態の更新が終われば、その結果を次の状態を更新する際の状態価値として使用します．

このアルゴリズムは、得られたデータをすぐに利用するので収束は早いとされる一方で、スイープの順番が大きく影響することになります．

Sutton本によれば、通常こちらの『その場更新（In-place）』型を用いるということです（4.1章）

方策反復評価のアルゴリズム

最後に、方策反復評価のアルゴリズムを示します．（これは『その場更新型』のアルゴリズムです）

$Input\; \pi ,\;the\;policy\;to\;be\;evaluated$
$Initialize\;an\;array\;V(s)=0,\;for\;all\;s\;\in S^+$
$Repeat$
$\qquad \Delta \leftarrow 0$
$\qquad For\; each\; s \in S:$
$\qquad \qquad v \leftarrow V(s)$
$\qquad \qquad V(s) \leftarrow \sum_{a}\pi(a|s)\sum_{s', r}p(s', r|s, a)[r + \gamma V(s')$ ]
$\qquad \qquad \Delta \leftarrow\;max(\Delta,|v-V(s)|)$
$until\;\Delta \lt \theta\;(a\;small\;positive\;number)$
$Output\;V \approx v_\pi$

ポリシーの改善

ここまでで、状態価値および行動価値、反復法による価値関数の更新について説明しました．ここから、ついにポリシー $\pi$ の改善に移っていきます．

ベストな行動と最適ポリシーの関係

ある状態 $s$ において、複数の行動が選択肢として与えらえているとします．この状態における最適なポリシー $\pi^*(s)$ とは、その名の通り、最もベストな行動を選ぶポリシーのことです．

ベストな行動はどうやって決めることができるかについて、以下の図を使って説明します．

f:id:shirakonotempura:20190131055121p:plain

緑の丸を起点の状態 $s$ になります．とりうる行動 $a$ は4つの黒丸で与えられています．この中のいずれかの行動がベストな行動になります．行動 $a$ を取った後で得られる収益は、状態遷移確率 $P^a_{ss'}$ を経て、報酬 $R^a_{ss'}$ および次の状態 $s'$ の価値関数 $V^\pi(s)$ で表されます．

f:id:shirakonotempura:20190131055137p:plain

グレーで囲んだこの収益は、各行動に対して計算されますので、この例の場合４つの収益が計算されます．この収益が最も高くなる行動を選ぶことが、状態 $s$ での最適なポリシー $\pi^*(s)$ となります．式で書くと、以下のように書くことができます．

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

ポリシーの改善

これまでの学習内容を整理します

あるポリシー $\pi$ があったとき、 - そのポリシーに従ったときの状態価値を求める（反復方策評価、iterative policy evaluation） - その状態での最適な方策 $\pi^*$ を求める（方策改善、policy improvement）

改善されたポリシー $\pi^*$ に従って新しい状態価値を求めれば、さらにその状態価値を使ってポリシーを改善していくことができます．

この繰り返しの作業を方策反復と呼びます

方策反復のアルゴリズム

初期化 Initialization

$V(s) \in R\;and \;\pi(s) \in A(s)\;arbitrarily\;for\;all\;s \in S$
方策評価 Policy Evaluation

$Repeat$
$\qquad \Delta \leftarrow 0$
$\qquad For\;each\;s\; \in S:$
$\qquad \qquad v \leftarrow V(s)$
$\qquad \qquad V(s) \leftarrow \sum_{a}\pi(a|s)\sum_{s', r}p(s', r|s, a)[r + \gamma V(s')$ ]
$\qquad \qquad \Delta \leftarrow\;max(\Delta,|v-V(s)|)$
$until \; \Delta \lt \theta$
方策改善 Policy Improvement

$policy{-}stable\leftarrow true$
$For\;each\;s \in S:$
$\qquad old-action \leftarrow \pi(s)$
$\qquad \pi(s) \leftarrow arg max_{a} \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')$ ]
$\qquad If\;old-action\neq \pi(s),\;then\;policy-stable\leftarrow false$
$If\;policy-stable,\; then\;stop\;and\;return\; V \approx v^* \; and \; \pi \approx \pi^*$ $;\; else\;go\;to\;2$