強化学習:プランニングと学習(その2)

f:id:shirakonotempura:20190209071355p:plain

はじめに

今回は、前回の記事(強化学習:プランニングと学習(その1))の続き、迷路問題での実装を行っていきます.

迷路問題に対するDyna-Qの導入

では、Sutton本に記載されている例題を使って、通常のQ学習と、Dyna-Qを比べてみます.

問題設定(6×9マス迷路):

f:id:shirakonotempura:20190209000458p:plain

  • 環境は上に示す6×9マスの格子世界の迷路
  • 図中Sはスタート地点、Gはゴールを示しています.グレーのマスは壁を意味する.
  • 壁を除く状態の数は47(S、G含む)
  • エージェントの行動は4種類(Up, Down, Left, Right)
  • 報酬はゴールに到達する行動に対してのみ+1が与えられ、それ以外は0とする.
  • ゴールに到達したらエピソードは終了し、スタートに戻り次のエピソードがスタート
  • 割引率\gammaは0.95 ‐ 行動価値の初期値は0.

エージェントのパラメータ

  • 学習率\alphaは0.1
  • 行動選択はε-greedy法で行い、εは0.1

50エピソードで学習終了としています.今回、比較のためプランニングを行うステップ数nを、『0回、1回、5回、50回』の4ケース実施しています.n=0のケースは通常のQ学習に相当します.

結果

下図に、横軸にエピソード、縦軸に1回のエピソード終了までに要したステップ数とした学習曲線を示します.50エピソードの学習を10回行い、その平均値をプロットしています.

f:id:shirakonotempura:20190209003529p:plain

いずれのケースも最終的には、学習が収束しています.しかし、Q学習が最も収束が遅く約30エピソードほどを要しています.一方、プランニングを考慮したDyna-Qのエージェントは、nを大きくするほど収束に要するエピソード数は減り、n=50のケースでは3エピソード目(episode = 2)には収束しています.

たった1度プランニングを行うn=1のケースですら、10エピソード未満で収束するのは驚きです.

Q学習とDyna-Qの結果にここまで差が出る原因を表したのが以下の図になります.

f:id:shirakonotempura:20190209012259p:plain

この図は、2番目のエピソード中でエージェントが見つけた方策を示しています.プランニングなし(Q学習)、右がプランニングあり(n=50)の結果になります.

プランニングを行わない場合、1エピソードが終了した時点で得られる方策はゴールに至る1手だけが学習されました.(そこでしか報酬は得られないので).

一方、プランニングを行う場合は、1エピソード終了時に得られる方策は最後の1手だけです^{*1}が、2エピソード目からは、n回のプランニングの中で価値関数が得られているマスに隣接するマスがサンプリングされる度、行動価値関数が更新されていくことになります.これが、エージェントが一歩動くたびに行われるわけですので、一気に広範囲で方策が見つけられることになるわけです.

*1:1エピソード中にも、実際にエージェントが1ステップ動くたびにn回プランニングを行いますが、ゴール以外では報酬の設定はしていないので、ゴールに到達するまで得られる報酬は0、行動価値の初期値も0なのでQ(s,a)は変化しません.

計算時間に関しては、ランダムに動き回る部分が入りますし10回程度回しただけの平均ですが、Dyna-Q(n=50)を3エピソードで約0.50秒、Q学習が30エピソードで約0.2秒前後でした(windows10、CPU機、詳細略).複雑な問題でなければQ学習に頑張ってもらってもいいのかもしれません.

モデルに誤りがある場合

ここまでは、モデルは正しく学習を行うという前提で話を進めてきました.しかし、実際の環境が確率的であることや、環境に変化が起きる可能性などを考慮するとモデルが常に正しいことを学習しているとは、考えない方がよいと言えます.

Dyna-Qは、実際の環境を使った更新も行いますのである程度環境の変化にも対応することが可能なのですが、環境がどのように変化をしたかによって少し状況が変わってきますので、以下例題を使いながら説明していきます.

妨害迷路問題(Blocking Maze Problem)

まず、初めにモデルが学習した方策より環境が悪化した場合の例を示します.つまり最短と思って学習した経路が使えなくなった.という状況を想定しています.

f:id:shirakonotempura:20190209021952p:plain

問題設定:

  • 環境は上に示す6×9マスの格子世界(迷路ではないです).
  • エージェントが1000ステップ行動を行った後、壁の位置が左図から右図のように変化します.
  • 図中Sはスタート地点、Gはゴールを示しています.グレーのマスは壁を意味する.
  • 壁を除く状態の数は46(S、G含む)
  • エージェントの行動は4種類(Up, Down, Left, Right)
  • 報酬はゴールに到達する行動に対してのみ+1が与えられ、それ以外は0とする.
  • ゴールに到達したらスタートにワープする.
  • 割引率\gammaは0.95 ‐ 行動価値の初期値は0.

エージェントのパラメータ

  • 学習率\alphaは1.0
  • 行動選択はε-greedy法で行い、εは0.1

実際の環境においてエージェントが3000ステップの行動を起こした時点で終了.累積報酬をカウントしています.なおDyna-Qアルゴリズムにおけるプランニングステップは10としています.また、Dyna-Q+で使用する\kappaは1.0e-4としています.

結果

下図に、横軸にステップ数とした累積報酬の履歴を示します.3000ステップの学習を20回行い、その平均値をプロットしています.Dyna-Q+の詳細は、後程説明します.

f:id:shirakonotempura:20190209044423p:plain

Dyna-QおよびDyna-Q+は、1000ステップ目までに右からの最短経路を見つけているように見えます.環境の変化後、いったんグラフの傾きが平になっています.エージェントは学習したはずの経路が突如なくなったため、右往左往して報酬を受け取ることができないためです.

しかし、その後1000ステップ程の停滞を抜けると、新しい左回りの道があることを発見し、そちらからの最適経路を見つけることができました.

比較のため、Q学習の結果も載せましたが、1000ステップでは最短経路を見つけることができていないので、比較になりませんでした.参考になるかわかりませんが、記事の最後にQ学習のみで妨害迷路問題を実施した場合の結果を載せています.

さて、このケースでは、モデルが学習した内容よりも最短経路が長くなる、つまり環境は悪化しています.今回の変化では最適と思った行動がとれなくなったため、別の方策を見つけることができたと言えます.

近道迷路問題( Shortcut Maze Problem)

次の例では、モデルが学習した内容よりも環境がよくなった場合の例を示します.状況としては最短経路と思っていた経路より、もっと最短な経路が見つかったという状況を想定しています.

f:id:shirakonotempura:20190209053357p:plain

問題設定:

  • 環境は上に示す6×9マスの格子世界(迷路ではないです).
  • エージェントが3000ステップ行動を行った後、壁の一部(右端)がなくなります. ‐ ステッピングサイズは50としています.
  • Dyna-Q+で使用する\kappaは1.0e-3としています

その他の設定は妨害経路問題と同じになります.

実際の環境においてエージェントが6000ステップの行動を起こした時点で終了.先と同じく累積報酬をカウントしています.

結果

妨害迷路問題と同様、横軸にステップ数とした累積報酬の履歴を示します.6000ステップの学習を5回行い、その平均値をプロットしています.

f:id:shirakonotempura:20190209054915p:plain

Dyna-Q+のアルゴリズムでは、近道の存在に気づき方策を改善することができています.しかし、Dyna-Qのアルゴリズムは近道が現れた後もその存在に気づかず、3000ステップ以前と同じ方策を取り続けていることがわかります.モデルは過去に経験した内容をベースに学習しているため、右に経路(近道)はないということを学習しています.また、左側からの経路は引き続き使用できるため、行動価値は更新され続けます.そのため、ステップが進むにつれて右側の近道に気づく可能性は小さくなっていくと考えられます.

では、この近道の存在に気づいたDyna-Q+のことを説明します.

Dyna-Q+アルゴリズム

Dyna-Q+では、モデルが出力する報酬に対して以下の式で探索ボーナス(exploration bonus)なるものを上乗せしています.

R+\kappa \sqrt{\tau}

ここで

R:ある遷移で得られるモデル上の報酬
-  \kappa:重みの係数(大きいほど探索を促す)
-  \sqrt{\tau}:その状態行動対が最後に選ばれてから経過したステップ数

この探索ボーナスによって、長い間探索がされていない箇所を探索することを促すことにつながるという仕組みです.当然、計算コストは高くなるのですが誤った解に収束するリスクを考えれば、探索する価値はあります.


参考:Q学習で妨害迷路問題

最後に、妨害迷路問題をQ学習だけで大体収束するまで計算してみましたので結果を載せておきます.大体5000ステップあたりで最短経路を見つけているようでしたので、5000ステップ以降で壁が動くように問題設定を変更しています.その後50000ステップまで計算しています.(Q学習なので計算コストはそこまで大きくないです)

f:id:shirakonotempura:20190209063238p:plain

まとめ

2回に分けて、Sutton本8章の内容を整理しました.
モデルのことがかなり理解できた気がします.

次回以降、価値関数の関数近似について勉強していきたいと思います.

ちなみに実は優先度スイープ(Prioritize Sweeping)という項目があるんですが燃え尽きました.