f:id:shirakonotempura:20190202132807j:plain

はじめに

前回は、TD（temporal-difference）学習の基本編として定式化とアルゴリズムの紹介を行いました．

強化学習：TD学習（基本編） - 他力本願で生き抜く（本気）

今回は、その中でも有名かつベーシックな学習アルゴリズムであるSARSAとQ学習（Q-learning）について整理していきます．Sutton本の6.4章からの話になります．

これは、私の学習用ノート．メモ、備忘録です

今回の内容、実装は以下の記事を参考にさせていただきました．

qiita.com

SARSA

SARSA法は、方策オン（on-policy）型制御のアルゴリズムで、実際の方策に従って得られる行動および状態を価値の更新に使用します．

具体的に数式で見ていきます．前回の最後に紹介したTD法での行動価値関数の更新式を以下に示します．見やすくするために、次の状態[tex:s{t+1}]および次の行動[tex:a{t+1}]を、 $s'$ および $a'$ で表します．

$$Q(s, a) \leftarrow Q(s, a) + \alpha[r' + \gamma Q(s', a') - Q(s, a)]$$

この式はある状態 $s \in S$ での行動 $a\in A(s)$ の価値 $Q(s,a)$ を、その行動によって観測された報酬 $r$ と次の状態 $s'\in S$ 、および、その状態で方策に従って選ばれた次の行動 $a' \in A(s')$ の行動価値 $Q(s', a')$ を使って更新しています．

これをバックアップ線図で書くと、以下のように書けます．（ちょっとペンを紛失してしまったので、図をそのまま使わせてもらいます．ごめんなさい）

f:id:shirakonotempura:20190202141653j:plain

この一連の状態 $s$ 、行動 $a$ 、報酬 $r'$ 、状態 $s'$ 、行動 $a'$ の頭文字をとってSARSAという名前が付けられています．

SARSAのアルゴリズム

Sutton本6.4章に記述されているアルゴリズムを以下に示します．

Sarsa (on-policy TD control) for estimating $Q \approx q_*$
Algorithm parameters: step size $\alpha \in (0, 1$ ]. small $\epsilon \gt 0$
Initialize $Q(s,a)$ , for all $s \in S+$ , $a \in A(s)$ , arbitrarily excerpt that Q(terminal, ・) = 0
Loop for each episode:
$\qquad$ Initialize $S$
$\qquad$ Choose $A$ from $S$ using policy derived from $Q$ (e.g., ε-greedy)
$\qquad$ Loop for each step of episode;
$\qquad \qquad$ Take action $A$ , observed $R, S'$
$\qquad \qquad$ Choose $A'$ from $S'$ using policy derived from $Q$ (e.g., ε-greedy)
$\qquad \qquad$ $Q(s,a) \leftarrow Q(s,a) + \alpha [R + \gamma Q(s',a') - Q(s,a)$ ]
$\qquad \qquad$ $S \leftarrow S'; \; A \leftarrow A' ;$
$\qquad$ until S is terminal

Q学習

引き続き、方策オフ型のアルゴリズムであるQ学習について整理していきます．
Q学習による行動価値の推定を数式で書くと次のようになります．

$$Q(s, a) \leftarrow Q(s, a) + \alpha[r' + \gamma \; argmax_{a'} Q(s', a') - Q(s, a)]$$

Q学習では、状態 $s$ を起点にまずε-greedy法により行動 $a$ を選択します．行動 $a$ の結果、報酬 $r'$ 、次の状態 $s'$ を得ます。ここまではSARSA法と変わりません。

その後の価値関数の更新が、SARSAとは異なり、max関数を用いて、最も価値の高い行動をとる状態行動対を用いて $Q(s,a)$ を更新しています．

価値関数を更新したあとの実際の行動、つまり $s'$ から実際に次の状態に進む際の行動 $a'$ は、価値関数更新時にmax関数で求められた行動ではなく、ε-greedy法を使って決めます．

バックアップ線図で書くと、以下のように書けます． f:id:shirakonotempura:20190202145253j:plain

Q学習のアルゴリズム

Sutton本6.5章に記述されているアルゴリズムを以下に示します．

Q-learning (off-policy TD control) for estimating $\pi \approx \pi$
Algorithm parameters : step size $\alpha \in (0, 1$ ]. small ε　> 0
Initialize $Q(s,a)$ , for all $s \in S+$ , $a \in A(s)$ , arbitrarily except that $Q(terminal, ・)$ =0
Loop for each episode:
$\qquad$ Initialize $S$
$\qquad$ Loop for each step episode:
$\qquad \qquad$ Choose $A$ from $S$ using policy derived from $Q$ (e.g., ε-greedy)
$\qquad \qquad$ Take action $A$ , observe $R, S'$
$\qquad \qquad Q(S,A) \leftarrow Q(S,A) + \alpha [R + \gamma \; argmax_{A} Q(S', A) - Q(S,A)$ ]
$\qquad \qquad S \leftarrow S'$
$\qquad$ until $S$ is terminal

実装

こちらに公開されているコードを使ってSARSAとQ学習の実装を行います．問題設定は、Sutton本の6.5章にあるCliff Walking（崖歩き問題）になります．

Cliff Walikng

崖歩きの問題では、以下のような格子状の環境を想定しています．

f:id:shirakonotempura:20190205032113p:plain

ルール
- エージェントは『up, down, right and left』の４つの行動をとることができる．
- エージェントは１つの行動をとるたびに-1の報酬を得る．
- エージェントの初期配置は左下のマス（スタート）．
- エージェントが右下のマス（ゴール）に到達した時点でエピソードは終了
- 『The Cliff』と書かれたエリアに移動した場合、-100の報酬を得て、エピソードは終了
- エピソード終了後、エージェントは左下のマスに戻り、次のエピソードが開始．

行動選択はε-greedy法で行いεは0.1、ステップサイズパラメータ（学習率） $\alpha$ は0.5としています．

結果

500エピソードの学習で得られた学習経路（最適行動）および学習曲線を以下に示します．
学習曲線の値は、500回エピソードの学習を1エポックとして、50エポック実施した平均の値を示しています．
なお、崖上（The Cliff）の行動に意味はありません．

SARSAの場合、実際に取る行動が価値の更新に影響するので、崖に落ちる行動をとってしまうと価値が下がります．ですので崖に落ちるという行動を避けながらゴールに向かう経路を学習しています．一方でQ学習の方は、ベストな行動で価値を更新するので、実際の行動で崖に落ちようが落ちまいが関係なく最短経路を学習しています．Q学習では落ちることのリスクを考慮に入れていませんので、SARSAよりも崖に落ちる回数は増えます．

そのため得られる報酬の平均を見れば、SARSAの方がQ学習を上回っていることが分かります．

SARSAであってもランダムな探索行動をとらなければ、崖に落ちるというリスクはないことになります．つまり実際にとる行動がベストアクション一択になり、落ちるリスクを避けて迂回する必要がなくなります．そのため、この2つの学習方法はεの値を０に近づけていくと等価になります．

SARSA（迂回（崖から離れる）経路を取っています）

['R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D']
['U', 'R', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'R', 'R', 'D']
['U', 'U', 'U', 'R', 'U', 'R', 'R', 'U', 'U', 'U', 'R', 'D']
['U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'G']

Q学習（崖のきわを通る最短経路を取っています）

['L', 'L', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'R', 'D', 'D']
['L', 'R', 'R', 'D', 'R', 'R', 'D', 'R', 'D', 'D', 'R', 'D']
['R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D']
['U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'U', 'G']

f:id:shirakonotempura:20190205032814p:plain