で見て理解するアルゴリズム
Powered by
ThothChildren
Main
Info
項目を検索中...
項目を検索中...
項目を検索中...
タイトルを検索中...
PolicyIterationで方策(Policy)が決まっていくイメージ
Policy Iterationでの強化学習のイメージを持てるような例を紹介します.

これだけ知っとく! : Policy Iteration概要
Points!
  • 目標:全ての状態\(s\)における行動\(a\)の確率を入れた配列\(policy[s][a]\)(方策/戦略)を算出(取るべき行動は高確率にする)
  • 既知:報酬関数, 遷移確率
  • 方策/戦略を更新し、それで価値(\(V[s]\))を更新し、更新した価値で再度方策を更新の繰り返し
  • 「最も価値(\(V[s]\))が高い行動」と「方策/戦略(\(policy[s]\))が選ぶ行動」が一致するまで更新
  • 更新式に沿って繰り返し全ての方策/戦略(\(policy[s]\))を更新
  • 価値更新式:
    \(V_{\pi}[s] = \displaystyle \sum_a \pi(a|s) \displaystyle \sum_{s'} P(s'|s, a) (R(s,a,s') + \gamma V_{\pi}[s'])\)
  • 方策更新式:
    \(policy[s] = \displaystyle \argmax_a \displaystyle \sum_{s'} P(s'|s, a) (R(s,a,s') + \gamma V[s']) \)
  • Value Iterationより早く収束
前置き! : 状況設定
下記の可視化は以下のようなルールに基づいたゲームです.このゲームでは今いるマスが「状態\(s\)」です.
  • よくある2Dを移動して高い報酬を目指すゲーム
  • スタートのマスからゴールのマスに移動できればOK
  • ダメージがあるマスとゲームオーバーになるマスあり
  • マスをクリックすることでマスの状態を変更可能
  • 歩くと少しずつ減点されるので最短でゴールを目指すと報酬が高くなります
  • パラメータを変更することで学習のされ方/可視化を変更可能
  • Game Startボタン : 迷路を解きます.
  • Game Start Slowボタン : 全体を一回更新して止まるを繰り返し迷路を解きます.
  • Game Start Super Slowボタン : 一つのマスを一回更新して止まるを繰り返し迷路を解きます.
可視化! : スタートからゴールまで行くGame
S
G
価値マップ
方策マップ
もうちょっと知っとく! : Policy Iterationの処理概要
PolicyIterationは、全ての状態(\(s\))に対する取るべき行動方策/戦略(\(policy[s]\))を持ちます.
またこの方策を元に全ての状態(\(s\))に対する価値(\(V[s]\))も計算します.この価値(\(V[s]\))は方策(\(policy[s]\))を元に計算する値で終始保持するものではありません.
この方策/戦略を更新してその戦略に基づいた価値を計算し、その価値で今度は方策を更新するというのを繰り返します.
「方策/戦略で選ばれる行動」と「方策から計算した価値から選ばれる行動」が一致したら、収束したものとして更新を終了します.

Policy Iteration手順
  1. 方策/戦略を初期化
  2. 価値方策を元に収束するまで計算
  3. 方策で選ぶ行動」と「価値を元に選ぶ行動」を比較して方策を更新.
    (選択した行動が異なれば方策を「価値で計算された行動」で更新.)
  4. 特に方策に変更がなければ終了.変更があれば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にします.
Facebookシェア Twitterツイート LINEで送る