Itsukaraの日記

最新IT技術を勉強・実践中。最近はDeep Learningに注力。

【DRL,Montezuma】Scoreが0になり回復しない原因の分析

Montezua's Revengeの強化学習で、下記のように、Scoreが0になり回復しない場合がありましたが、原因を少し分析してみました。

Scoreが0になり回復しない状況調査

http://54.238.214.79/OpenAIGym/montezuma-x1/log.gcp10.montezuma-x-yaml-pscm-ff-fs2.r.png

Scoreが0になった後は、ROOM#1でPanama Joeが死にまくるのかと思っていましたが、これは誤っていることが分かりました。下記は、どの部屋でkillが起きているか(kill頻度:一定stepあたりのkill回数)を図示したものです。なお、凡例に書かれた数字が部屋の番号です。
f:id:Itsukara:20170108190907p:plain

Scoreが0になる直前で(約28 Mstep)、ROOM#1のkill頻度が高まっていますが、28 Mstep以降は、kill頻度がほぼ0なのがわかります。ほぼ0の部分を拡大したものが下記です。
f:id:Itsukara:20170108191507p:plain

ほぼ0ではあるものの、完全に0ではなく、多少のkillが発生していることが分かります。つまり、あまりkillされない範囲で、微妙に移動しているようです。(この部分の動画を撮っておけば、もっとハッキリしたのですが...*1 )

ちなみに、先頭から2つめの図を見ると、Scoreが0になる直前では、ROOM#2のkill頻度だけでなく、ROOM#2、ROOM#7のkill頻度も増えています。

下記は、各部屋の訪問頻度を図示したものです。Scoreが0になる直前で、ROOM#7の訪問回数が増えていることが分かります。
f:id:Itsukara:20170108195825p:plain

原因分析/推測

これらから、下記のような現象が起きているのではないかと推測しています。

  • ROOM#7や他の部屋での学習の副作用として、ROOM#1でkeyを入手できなくなる(NNの値が、そのように変化するということ)。
  • これにより、ROOM#1から脱出できなくなり、Scoreは100点以下になる。
  • また、実rewardが0になるので、各地点(実際はstatus)でのVが順次減少する。
  • 更に、ROOM#1内の地点(実際はstatus)は通過頻度が高く、pseudo-rerawdはほぼ0。これにより、Vを増加させるものが全く無い状態となる。
  • そのため、ROOM#1内で、僅かなpseudo-rewardだけに基づいて学習が起こり、killが起きない程度の僅かな動きだけになる。
  • 上記全体の結果として、Scoreを取得する上で重要なルートほど、通過回数が非常に多いので、pseudo-rewardは0に近く、一度Vが0に近くなると回復することはない。

上記推測が正しいとすると、pseudo-rewardだけに基づいた学習では、実rewardを取れる所まで辿り着けるようになるものの、その地点へのルートの学習が一度失われると、回復しないということとなります。そのために、学習が非常に不安定になるのだと思います。

上記は、A3Cで学習ですが、Double DQNでは、一度学習したパスを覚えておき、後で利用するので、一度Scoreが0になっても、過去に学習したパスでのVに基づいて再学習が行われ、安定な学習に寄与できるのだと思います。

対策案 (Replay Memoryの導入/活用)

逆に、A3Cでも、一度学習したパスをReplay Memoryに覚えておき、後で利用するようにすれば、学習が安定すると思われます。ただ、メモリ量も限られるので、どのパスを覚えておくのが良いか、判断が難しいですね。Scoreは高いほうが良い、Score取得時のLivesは多いほうが良い、点数を取得するまでのsteps数は少ないほうが良い、などの判断基準が考えられますが、これらに対して、どのように重み付けするのが良いか、難しそうです。1つの案としては、重み付けも学習すれば良いかもしれませんが...

対策案のためのメモリ量削減

なお、記憶するパス数や長さを制限する以外に、直接メモリ量を減らすことも可能です。以前に実験した結果として、pythonlzmaでパスを圧縮すると、メモリ量が約1/40になり、学習速度(steps/h)への影響は16%程度で済むことが分かっています。

実際、現在でも、High Score取得動画や、新しいROOM訪問動画を出力するために、全てのthreadの全ての学習で、GAME OVER直前までのパスを覚えています。実は、パスの圧縮を行う前は、学習途中でメモリ量が16GBを超え、メモリ不足になることもあったのですが、パスの圧縮を行うことにより、現状のメモリ量は4GB程度で済んでいます。

別の対策案 (Mile Stone)

ちなみに、Replay Memory以外にもメモリ量が非常に少ない方法がありそうと思っています。Replayするパスを覚えるのではなく、学習に有効なパスの幾つかの場所(status)をMile Stoneとして覚えておき、そのMile Stoneでは、擬似rewardとしてMile Stoneポイントを与えることが考えられます。ただ、この場合も、どれをMile Stoneにするか、どのようにMile Stoneを更新するかなど、課題が色々ある気がします。

今後の進め方

最近、ウィークディは仕事が忙しく、土日も私用で忙しく、なかなかDeep Learningで遊べなくなってきていますが、できるだけ時間を作って、Replay Memoryの導入・利用処理や、Mile Stoneを実装していこうと思います。

実は、他にも色々とアイデアがあるのですが、実装の手間・時間、その効果を確認するために必要なITリソースや時間などが、膨大に必要なため、なかなか難しい状況です。

*1:別の学習で同様の現象が発生した際の動画が取れたので一応載せておきます。何のモチベーションもないため、何しもしない怠惰なPanama Joeに戻ってました。youtu.be