【DRL,Montezuma】Scoreが0になり回復しない原因の分析
Montezua's Revengeの強化学習で、下記のように、Scoreが0になり回復しない場合がありましたが、原因を少し分析してみました。
Scoreが0になり回復しない状況調査
Scoreが0になった後は、ROOM#1でPanama Joeが死にまくるのかと思っていましたが、これは誤っていることが分かりました。下記は、どの部屋でkillが起きているか(kill頻度:一定stepあたりのkill回数)を図示したものです。なお、凡例に書かれた数字が部屋の番号です。
Scoreが0になる直前で(約28 Mstep)、ROOM#1のkill頻度が高まっていますが、28 Mstep以降は、kill頻度がほぼ0なのがわかります。ほぼ0の部分を拡大したものが下記です。
ほぼ0ではあるものの、完全に0ではなく、多少のkillが発生していることが分かります。つまり、あまりkillされない範囲で、微妙に移動しているようです。(この部分の動画を撮っておけば、もっとハッキリしたのですが...*1 )
ちなみに、先頭から2つめの図を見ると、Scoreが0になる直前では、ROOM#2のkill頻度だけでなく、ROOM#2、ROOM#7のkill頻度も増えています。
下記は、各部屋の訪問頻度を図示したものです。Scoreが0になる直前で、ROOM#7の訪問回数が増えていることが分かります。
原因分析/推測
これらから、下記のような現象が起きているのではないかと推測しています。
- 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つの案としては、重み付けも学習すれば良いかもしれませんが...
対策案のためのメモリ量削減
なお、記憶するパス数や長さを制限する以外に、直接メモリ量を減らすことも可能です。以前に実験した結果として、pythonのlzmaでパスを圧縮すると、メモリ量が約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リソースや時間などが、膨大に必要なため、なかなか難しい状況です。