強化学習、マルチエージェント強化学習、その他機械学習全般

機械学習関連のことをまとめていきます。強化学習関連が多いかもしれません

【強化学習】SARSAとQ Learningとの違い

SARSAとQ Learningの違いについて参考文献をもとにお話したいと思います。
SARSAとQ Learningのそれぞれのアルゴリズムとプログラムについては下記の記事で紹介しています。

www.tcom242242.net

www.tcom242242.net

SARSAとQ Learningの学習方法の違い

SARSAとQ Learningの違いは学習に用いるTD誤差にあります。
いかにSARSAとQ Learningの更新式を示します。
まず、Q Learningの更新式、 $$ Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma \color{red}{\max_{a' \in A}Q(s',a')}-Q(s,a)) $$

次にSARSAの更新式、
$$ \begin{eqnarray} Q(s, a) \leftarrow Q(s, a) + \alpha (r +\gamma \color{red}{Q(s', a')} - Q(s, a)) \end{eqnarray} $$ SARSAは遷移先の状態において実際に取る行動の情報$Q(s', a')$を用いて学習し、
Q Learningでは、遷移先の最大行動価値$\max_{a' \in A}Q(s',a')$を用いて学習します。
SARSAは現在の方策に依存し、Q Learningは方策には依存しないのが特徴です。
また、Q Learningは遷移先状態の良い部分しか見ていないというものも大きな特徴です。

では、2つのトイプロブレムで、どのような性能差がでるかを
崖があるグリッドワールドで試してみます。

崖があるグリッドワールド

通常のグリッドワールドとは異なり、崖があるグリッドワールドを用いて、評価します。
図で表すと以下のような問題になります。

f:id:ttt242242:20190404180402j:plain

エージェントが崖に行くと報酬が-100となり、さらにスタート地点に戻されます。 それ以外の地点ではひたすら-1の報酬が得られるようなゲームです。

プログラム

githubに挙げました。
クローンして、run.pyを実行するとグラフが出力されます。

github.com

実験と考察

この実験では$\epsilon$-greedyを用いて、$\epsilon=0.1$に固定して学習を行います。
複数回試行し、、エピソード毎の平均報酬で評価します。
以下のグラフがQ LearningとSARSAによる実験結果です。

[f:id:ttt242242:20190404175948j:plain:250]
Q LearningとSARSAの比較

横軸はエピソード、縦軸が累積報酬を表しています。
SARSAのほうがQ Learningに比べて良い報酬を得ていることがわかります。
これはなぜか?
各手法によって得られた方策を見てみます。
プログラムで出力されただと見にくいので、図で示します。

f:id:ttt242242:20190404180311j:plain:h200
Q Learningが学習した方策

f:id:ttt242242:20190404180110j:plain:h200
sarsaが学習した方策

基本的に参考文献と変わりません。

Q Learningは危険(崖に近い)な近道を学習して、
SARSAは安定した方策を学習してます。

なぜそのような結果になったかというと
Q Learningは遷移先状態の最大行動価値だけを用いるため、
単純にゴールがどれだけ近いかのみを見みます。
そのため、近い道を見つけています。
逆に言えば、遷移先状態の最大行動価値以外の価値は見ないため、
危険かどうかは考慮ぜず行動します。
崖に近い道を選択しているので、 探索行動によってと崖から落ちているため、
報酬が小さくなっています。

一方で、SARSAは $\epsilon$-greedyで、$\epsilon$を0にしない限り、
遷移先状態のすべての行動価値を考慮して学習します。
そのため、危険な道も考慮して学習することになり、
安全な道を学習したと言えます。

もちろん最終的に$\epsilon$を0にした場合には両者とも
最も近い道を最適経路として学習します。

参考文献

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る