で見て理解するアルゴリズム
Powered by
ThothChildren
Main
Info
項目を検索中...
項目を検索中...
項目を検索中...
タイトルを検索中...
SARSAの動きのイメージ
SARSAでの強化学習のイメージを持てるような例を紹介します.

これだけ知っとく! : SARSA概要
Points!
  • 目標:状態\(s\)における行動\(a\)の価値\(Q[s][a]\)を試行錯誤しながら算出
  • 未知:報酬関数, 遷移確率
  • 与えられた回数、エピソードを経験.各エピソードではゲームを学びながら高い報酬を得られる行動を選択.
  • 報酬や遷移確率が未知なため、手探りに良い手段を探索. 行動選択時に数割ランダムに選択して残りは知識から最善手を選択.
  • Q-Leaningは更新に際して次の状態の価値は最もQ値が高い行動を選択した場合で見積もったが、SARSAでは次の選択はポリシーに沿って行動を選択した場合の見積もり
  • 更新式:
    \(a_{next} \leftarrow policy(s_{t+1})\)
    \(Q[s_t][a] \leftarrow Q[s_t][a] + \alpha (r_{t+1} + \gamma Q[s_{t+1}][a_{next}] - Q[s_t][a]) \\ = (1-\alpha)Q[s_t][a] + \alpha(r_{t+1} + \gamma Q[s_{t+1}][a_{next}])\)
前置き! : 状況設定
下記の可視化は以下のようなルールに基づいたゲームです.このゲームでは今いるマスが状態「状態\(s\)」です.
  • よくある2Dを移動して高い報酬を目指すゲーム
  • スタートのマスからゴールのマスに移動できればOK
  • ダメージがあるマスとゲームオーバーになるマスあり
  • 歩くと少しずつ減点されるので最短でゴールを目指すと報酬が高くなります
  • マスをクリックすることでマスの状態を変更可能
  • パラメータを変更することで学習のされ方/可視化を変更可能
  • 「Random」はランダムに選択された行動できたことを示す表示
  • 番号は移動してきた順番
  • 赤や緑の色はQ値の具合を表現
  • Game Startボタン : 迷路を解きます.
  • Game Start Slowボタン : 1エピソードを体験して止まるを繰り返し迷路を解きます.
  • Game Start Super Slowボタン : 1行動ごとにQ値表示を繰り返し迷路を解きます.
可視化! : スタートからゴールまで行くGame
S
G
もうちょっと知っとく! : SARSAの処理概要
SARSAは、Q-Learningとほとんど処理は同じですが一点異なります.
更新時に次の状態での行動\(a_{next}\)を選択して、その行動を取ったときに得られるだろうQ値で\(Q[s_t][a]\)を更新します.


SARSA手順
  1. Q値(\(Q[s][a]\))を初期化
  2. 指定された回数、下記3.~8.のループでゲームをプレイ
  3. ゲームを初期化. \(t=0\) 初回は必ずランダムな行動\(a\)を選択
  4. 行動\(a\)を実行し、ゲームから報酬\(r\)と次の状態\(s_{t+1}\)を得る.
  5. 一定割合でランダムな行動\(a_{next}\)を選択. 残りの割合でQ値\(Q[s_t][a]\)の最も高い行動\(a_{next}\)を選択.(\(\varepsilon-greedy\)法の場合)
  6. \(Q[s_t][a] \leftarrow Q[s_t][a] + \alpha (r_{t+1} + \gamma Q[s_{t+1}][a_{next}] - Q[s_t][a]) \\ = (1-\alpha)Q[s_t][a] + \alpha(r_{t+1} + \gamma Q[s_{t+1}][a_{next}])\)
  7. \(a \leftarrow a_{next}\)
  8. ゲームが終了していれば、3.へ. していなければ4.へ.


SARSA : 価値の更新
Q値の更新は

$$Q[s][a]:状態sで行動aの価値$$ $$r_{t+1}:状態s_tから状態s_{t+1}へ遷移したときの報酬$$ $$\alpha:学習率$$ $$\gamma : 報酬の割引$$
$$Q[s_t][a] \leftarrow Q[s_t][a] + \alpha (r_{t+1} + \gamma Q[s_{t+1}][a_{next}] - Q[s_t][a]) \\ = (1-\alpha)Q[s_t][a] + \alpha(r_{t+1} + \gamma Q[s_{t+1}][a_{next}])$$

で行われます.
Q値は行動を実行した結果に基づいて一つ前の状態を更新します.その際、 これまで持っているQ値\(Q[s_t][a]\)と新しいQ値\((r_{t+1}+\gamma Q[s_{t+1}][a_{next}])\)を比率\(\alpha\)で更新されます.
学習しているとき、次の状態\(s_{t+1}\)で取る行動\(a_{next}\)を決めてしまいその状態\(s_{t+1}\)でその行動\(a_{next}\)のQ値で見積もりを行なっていることが、Q-Learningとの違いになります.


Q-LearningとSARSAの違い
くどいですが、もう一度その違いだけに注目して述べておきます.

Q-Learning
  1. 状態\(s_t\)で行動\(a\)を選択(\(\varepsilon-greedy\)法等)
  2. 状態\(s_t\)で行動\(a\)を実行
  3. \(Q[s_t][a]\)を\(s_{t+1}\)で最大のQ値の行動\(a_{nextbest}\)をとるものとして\(Q[s_{t+1}][a_{nextbest}]=max_a Q[s_{t+1}][a]\)で更新
SARSA
  1. 状態\(s_t\)で行動\(a\)を実行
  2. 状態\(s_{t+1}\)で行動\(a_{next}\)を選択(\(\varepsilon-greedy\)法等)
  3. \(Q[s_t][a]\)を\(s_{t+1}\)で行動\(a_{next}\)でのQ値で更新
  4. 行動\(a\)に行動\(a_{next}\)を代入

この差があることで、Q-Learningは常に最も効率がいい解を選択しますが、SARSAはより慎重な解を選択するようになります.
SARSAは常に行動選択するときも見積もる時も同じポリシー(\(\varepsilon-greedy\)法等)で動くため、On-Policyと呼び、 Q-Learningは行動選択するときはポリシー(\(\varepsilon-greedy\)法等)で見積もる時はQ値が最大になる行動を選択するためOff-Policyと呼びます.
Facebookシェア Twitterツイート LINEで送る