PolicyIterationは、全ての状態(\(s\))に対する取るべき行動方策/戦略(\(policy[s]\))を持ちます.
またこの方策を元に全ての状態(\(s\))に対する価値(\(V[s]\))も計算します.この価値(\(V[s]\))は方策(\(policy[s]\))を元に計算する値で終始保持するものではありません.
この方策/戦略を更新してその戦略に基づいた価値を計算し、その価値で今度は方策を更新するというのを繰り返します.
「方策/戦略で選ばれる行動」と「方策から計算した価値から選ばれる行動」が一致したら、収束したものとして更新を終了します.
Policy Iteration手順
- 方策/戦略を初期化
- 価値を方策を元に収束するまで計算
- 「方策で選ぶ行動」と「価値を元に選ぶ行動」を比較して方策を更新.
(選択した行動が異なれば方策を「価値で計算された行動」で更新.)
- 特に方策に変更がなければ終了.変更があれば2.から再度計算
Policy Iteration : 価値の更新
価値の更新は
$$\pi(a|s):状態sのときにaを取る確率(方策/戦略)\\(初期値はどの行動も等確率, 更新するときに選択すべき行動のみ1とする)$$
$$V[s]:状態Sの価値$$
$$P(s'|s,a):状態sから行動aをとって状態s'になる確率$$
$$R(s, a, ,s'):状態sから状態s'へ行動aで遷移したときの報酬$$
$$\gamma : 報酬の割引$$
$$V[s] = \displaystyle \sum_a \pi(a|s) \displaystyle \sum_{s'} P(s'|s, a) (R(s,a,s') + \gamma V[s'])$$
で行われます.
この式のままだとわかりにくいので二つに分解すると,
まず大枠からいえば
$$V[s] = \displaystyle \sum_a \pi(a|s) ExpectedReward(a)$$
式の意味するところは、
「その状態\(s\)から各行動\(a\)で期待できる報酬\(ExpectedReward(a)\)とその行動を取る戦略の確率\(\pi(a|s)\)を掛けて全ての合計値をその状態の価値とする」.
実装では,方策/戦略\(\pi(a|s)\)は配列で持ち\(policy[s]\) = {\( RIGHT:0, LEFT:1, UP:0, DOWN:0\)}のようにして持っています.そのpolicy[s]と期待報酬を掛け合わせて足し合わせることになります.
各動作\(a\)を取った時の期待される報酬\(ExpectedReward(a)\)は
$$ExpectedReward(a) = \displaystyle \sum_{s'} P(s'|s, a) (R(s,a,s') + \gamma * V[s'])$$
\(a\)の行動をして遷移しうるすべての次の状態で得られる報酬を計算します.
具体的には「遷移して得られる報酬(\(R(s,a,s')\))」と「期待される未来の報酬(\(V[s']\))」の合算した報酬
を計算しています.
合算した期待報酬にその状態になる確率\(P(s'|s,a)\)をかけることで
その状態に遷移した時の期待報酬を計算します(\(P(s'|s, a) (R(s,a,s') + \gamma * V[s'])\))
まとめると
ある行動\(a\)を選択した時の全ての遷移先での期待報酬を足し合わせた値をその行動\(a\)を取った時の期待報酬(\(ExpectedReward(a)\))とします.
全ての行動\(a\)に関して、上記「期待報酬」と「方策/戦略で決められている行動の確率」を掛け合わせた値を足し合わせた価値を状態の価値(\(V[s]\))としています.
Policy Iteration : 方策の更新
価値を計算し直したら、次は方策を更新します.
上で計算した価値を用いて、最もよい行動を次のように算出し、その行動を状態\(s\)で取るべき行動として方策を更新します.
$$policy[s] = \displaystyle \argmax_a \displaystyle \sum_{s'} P(s'|s, a) (R(s,a,s') + \gamma V[s'])$$
方策は\(policy[s]\) = {\( RIGHT:0, LEFT:1, UP:0, DOWN:0\)}のように持っています.
初期化したときのみ、全ての行動の確率を等しくしておき、
更新するときには、最適とされる行動の確率を1にし、他を0にします.