今回やること
TD法を用いた制御方法であるSarsaとQ学習の違いについて解説します。下記の記事を参考に致しました。
コードはgithubにアップロードしています。
【強化学習】SARSA、Q学習の徹底解説＆Python実装
強化学習 : SarsaとQ学習
クッキーの日記: SarsaとQ学習の違い
いものやま。: 強化学習について学んでみた。（その19）
Platinum Data Blog by BrainPad: 強化学習入門 ～これから強化学習を学びたい人のための基礎知識～
はじめに
前回の記事でTD（Temporal Difference）法を用いて価値関数の推定をおこないました。TD法は
- ブートストラップを用いることができる（後続状態の価値を現在の価値推定に使える） ←動的計画法の利点
- 環境のダイナミクスがわからなくても、サンプリングを用いて価値を推定できる ←モンテカルロ法の利点
のように、動的計画法とモンテカルロ法のいいとこ取りをした方法です。詳細は以下
価値関数の更新は、
$$V(s_t) ← V(s_t) + \alpha[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)] (1)$$
で表すことができます。この式を日本語で説明すると、
新しい推定値 ← 古い推定値 + ステップサイズ [ 最新の更新データ ー 古い推定値 ]
となります。
TD法を用いた最適方策決定
推定した価値関数から最適な方策を決定します。その際、状態価値関数$V(s)$よりも行動価値関数$Q(s,a)$を用います。理由は、状態行動対に対して価値がわかっていれば、ある状態のときに最も価値の高い行動を（その時点での）最適行動とすることができるからです。
$$BestAction(s) ← argmax_{a} Q(s,a) (2)$$
ただし、常に最適行動を選択すると（これをgreedyな方策と呼びます）、リスクを取ってより最適な方策を探索することができないため、一定の確率$\epsilon$でランダムな行動をとるようにします。これを$\epsilon$-greedy法と呼びます。詳しくは以下
今さら聞けない強化学習(8): モンテカルロ法でOpenAI GymのCartpoleを学習
ちなみに、greedy手法とは、$\epsilon$=0の時の$\epsilon$-greedyと言えます。
Sarsa
それでは、TD法と$\epsilon$-greedy法を組み合わせて、価値関数の推定と最適方策を同時に求めて行きましょう。
まず、TD法による行動価値関数$Q(s,a)$の更新ですが、式(1)と全く同様に表せます。すなわち、
$$Q(s_t, a_t) ← Q(s_t, a_t) + \alpha[r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)] (3)$$
となります。ただし、状態s, s'からのとる行動a, a'は$\epsilon$-greedy法により決定します。
このままだと、$t$の添字が見にくいので、次の状態、行動をそれぞれs', a'として表します。
$$Q(s, a) ← Q(s, a) + \alpha[r' + \gamma Q(s', a') - Q(s, a)] (3')$$
この更新方法を右辺の変数の頭文字をとってSarsa法と呼びます。エピソードの更新は$\epsilon$-greedy手法に従います。これを図示してみましょう。
$\epsilon$-greedy手法に従い、状態$s$からとる行動$a$を選択します。それにより報酬$r'$と次の状態$s'$を得ます。
価値関数$Q(s,a)$の更新は、次の行動状態対$s', a'$から更新されます。実際の方策（$\epsilon$-greedy）に従って価値を更新するのでSarsaは方策オン手法と呼ばれます。
価値関数を更新したあとは、行動$a'$を実行し、エピソードを進めて価値関数を更新することを繰り返します。
Q学習
Sarsaの他に別の方法もあります。その一つがQ学習です。Q学習の更新式を示します。
$$Q(s, a) ← Q(s, a) + \alpha[r' + \gamma , max_{a'} Q(s', a') - Q(s, a)] (4)$$
Sarsaは価値更新に用いる後続状態に$\epsilon$-greedyを用いて、一定のランダム性を織り込むのに対し、Q学習はmax関数によって最も価値の高い行動を一律に(グリーディに)選択するところが異なります。
Q学習のバックアップダイアグラムを示します。
Q学習では、状態sをスタートとしてまず$\epsilon$-greedy法により行動$a$を選択し、実行します。その結果、報酬$r'$、$s'$を得ます。ここまではSarsaと変わりません。
その後の価値関数の更新ですが、Sarsaとは異なりmax関数を用いて、最も価値の高い行動をとる状態行動対を用いて$Q(s,a)$を更新します。
ここで注意してほしいことが、価値関数を更新したあとの実際の行動です。s'から実際に進む次の行動は、価値関数更新時にmax関数によって求めた行動ではなく、$\epsilon$-greedy法により求めます。
注；もちろん、両者の行動がたまたま一致することもありますが、本質的には別の行動です。
図では、次に進むエピソードがmaxによって選ばれた行動ではなく、$\epsilon$-greedy法により選ばれた行動に繋がっていることを確認してください。Sutton本では、このことを強調していなく、理解するのに時間がかかりました。。一度気がつくと何てことはないのですが、SarsaとQ学習の違いがあんまりわかっていない、という方はこの辺りが曖昧だったりしないでしょうか（私がそうでした。。）
Q学習では、実際に進む行動（方策）と価値関数の更新に用いる行動（方策）が異なります。そのためQ学習は方策オフの学習手法と呼ばれます。
SarsaとQ学習の違い
価値関数更新のアルゴリズムの違いが、方策（最適行動）決定に及ぼす影響を示します。
問題設定として、崖歩き（criff walk）を考えます。
エージェントはスタート地点（S）から出発し、上下左右のいずれかの行動をとります。
その際、一歩歩くたびに-1の報酬（つまり罰則）を得ます。ただし、灰色で示したところは崖（criff）になっていて、ここに移動すると-100の報酬を得てスタート地点に強制的に戻されます。（エピソードはそこで終わります）。
ゴール（G）につくと＋100の報酬です。グリッドの外にでるような行動は無効ですが-1の罰則は課されます。
最適行動をSarsaおよびQで求めます。
パラメータ
- $\gamma$ = 0
- $\alpha$ = 0.1
- $\epsilon$ 0, 0.1, 0.5 ←$\epsilon$が結果に与える影響を考察します。
- episode数: 5000
結果
epsilon: 0.1
$\epsilon$ = 0.1の時のSarsaおよびQの最適行動を以下に示します。
Sarsa↓!
Q学習↓
各状態での最適行動を矢印で示しています。崖の部分およびゴールにはとどまらないので、この部分の矢印は意味を持ちません。
また、スタートからゴールまで最適行動に従った時の経路を蛍光色でハイライトしています。
これをみると、Q学習では最短経路を通っているのに対して、Sarsaではグリッドの上方へ遠回りしているのが分かります。
Sarsaでは価値更新に$\epsilon$-greedy法で選択した行動を用いるため、崖に落ちた時の大きな罰則を価値関数の更新に組み込まなければなりません。そのため、Sarsaでは安全策をとって遠回りをして、崖に落ちた時の罰則を避けます。
対してQ学習では、最短経路をとっています。なぜなら、Q学習の場合、価値関数の更新に最大価値を取る行動を能動的に選択できるため、崖ギリギリを攻めることになんらデメリットがありません。
なお、Q学習でも実際の移動には$\epsilon$-greedy法を用いるため、行動の結果崖に落ちます。むしろ、崖ギリギリを責めているので落ちる頻度はSarsaよりも高くなります。Q学習は、実際の行動と価値関数の更新に用いる行動が違うことに注意してください。
学習結果のプロットを見てみましょう。縦軸は各エピソードごとの報酬の総額、横軸は反復して学習したエピソード数を示しています。
赤がQ学習、青がSarasaで、半透明のデータが生データ、実線は移動平均（N＝50）を示しています。生データが下に大きく振り切れている（見にくいですが、スパイク状のノイズになっています。）のは崖に落ちた時の-100点を反映しているからです。
Q学習の方が崖ギリギリを攻めるため、崖に落ちる頻度が高く、移動平均の結果はQ学習の法が低くなっています。
ただし、生データの学習曲線の上限値はQ学習が88点、Sarsaが86点とSarsaの法が2点低くなっています。これは、Sarsaの経路がQよりも1段上方を通って迂回しているため、上・下の2アクション余計に必要だからです。
Sutton本では、移動平均の結果だけを見せて、”Sarsaに比べてオンラインの性能が劣る”と書いてあります。生データの上限値とスパイク（崖落下）の頻度まで考慮して議論しないと、議論が不十分だと思います。
epsilon: 0.5
epsilonをさらに大きく、よりランダムに行動するようにした時の結果を示します。
Sarsa↓
Q学習↓
よりランダムに行動するため、崖に落ちるリスクが高まったので、Sarsaではさらに迂回する戦略をとっています。Q学習の結果は変わりません。
epsilon: 0.0
次は逆にepsilonを0にしてランダム性を無くしてみます。ただ、学習初期からランダム性をなくすと探索を行わないため、初めの1000エピソードは、$\epsilon$を0.1から0まで直線的に減少させ、その後の4000エピソードは$\epsilon$=0で学習させました。
Sarasa↓
Q学習↓
Sarasaでも最短経路を学習していますね。$\epsilon$=0ですから自分の思った通りの方向に進めるので迂回する必要がなくなります。Sarsaの式（3'）とQ学習の式（4）は$\epsilon$=0の時に等価なので、この二つの学習は同じことをしています。
SarsaとQ学習のどちらを用いるべきか
*筆者の感想： *
実際の学習時には、$\epsilon$を減少させていって最終的に0にすることが多いと思います。SarsaとQ学習のどちらが良いかについてですが、SarsaもQ学習も最終的な結果は同じところに収束するのでどちらでも良いような気がします。ただし、学習初期の$\epsilon \neq$0では、挙動が違います。学習終端と同様の方策を獲得しているQ学習の法が良いような気がします。強化学習と言えばQ学習でSarsaがあまり使われていないのはこのあたりが理由なのか、それとも他に理由があるのかもしご存知でしたらコメントいただけると幸いです。
##まとめ
- SarsaとQ学習の価値関数の更新式を示した
- Sarsaは$\epsilon$-greedyに従って行動、価値関数の更新を行う（方策オン）
- Q学習は$\epsilon$-greedyに従って行動し、最適価値をとる行動に従って価値関数を更新する（方策オフ）
- SarsaとQ学習の学習結果の違いを示した
- 得られた移動経路
- Sarsaでは価値更新に実際に取った行動を勘案するため、安全策をとった方策を獲得する
- Q学習では実際に取られた行動を勘案しないため、最短の経路を学習する
- 得られる報酬
- Sarsaは安全策を取る。その分最高収益は理論上の最高値より低い
- Q学習はガンガン攻める。学習時の収益は低いが最適方策を獲得する
- $\epsilon$=0の時、SarsaとQ学習は一致する。
- 得られた移動経路