TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

MuZeroの論文を読む その３（結果）

MuZero 強化学習

結果

測定条件

  • それぞれのケースで、K = 5の仮想ステップでMuZeroを訓練した。
  • ボードゲームではサイズ2048、アタリではサイズ1024の100万ミニバッチで訓練した。
  • 訓練と評価の両方で、MuZeroはボードゲームの各探索に800回のシミュレーションを使用し、Atariの各探索に50回のシミュレーションを使用した。
  • 表現関数は、AlphaZeroと同じ畳み込みおよび残差アーキテクチャを使用するが、20ではなく16の残差ブロックを使用する。
  • ダイナミクス関数は表現関数と同じアーキテクチャを使用し、予測関数はAlphaZeroと同じアーキテクチャを使用する。
  • すべてのネットワークは256の隠れプレーンを使用する（詳細については、「Methods」を参照）。

各ゲームの訓練全体のパフォーマンス

  • 図2は、各ゲームの訓練全体のパフォーマンスを示している。
  • 囲碁では、MuZeroはAlphaZeroのパフォーマンスをわずかに上回ったが、探索木のノードごとの計算量は少なくなった（AlphaZeroの20ブロックと比較して、MuZeroの評価ごとに16残差ブロック）。
  • これは、MuZeroが計算を探索木にキャッシュし、ダイナミクスモデルの各追加適用を用いて局面をより深く理解できることを示唆している。
図2：チェス、将棋、囲碁、Atariの訓練全体でのMuZeroの評価

f:id:TadaoYamaoka:20191125231748p:plain

  • X軸は、数百万の訓練ステップを示している。
  • チェス、将棋、囲碁の場合、y軸はEloレーティングを示す。 これは、両プレイヤーが1手につき800シミュレーションを使用してAlphaZeroに対してゲームをプレイすることによって確立される。
  • MuZeroのEloは青い線で、AlphaZeroのEloはオレンジ色の水平線で示されている。
  • Atariの場合、57のゲームすべてにわたる人間の正規化された平均（実線）および中央値（破線）がy軸に表示される。
  • R2D2のスコア（モデルフリーRLに基づいたこのドメインの従来技術）は、オレンジ色の水平線で示されている。
  • Atariのパフォーマンスは、4タイムステップごとに50回のシミュレーションを使用して評価され、その後、以前の研究*1と同様に、選択されたアクションを4回繰り返した。

Atariの結果

  • Atariでは、MuZeroはArcade Learning Environmentの57のゲームで平均および中央値の両方の正規化スコアの最先端を達成し、57のゲームのうち42で以前の最先端のメソッドR2D2*2（モデルフリーアプローチ）を上回り、すべてのゲームで以前の最高のモデルベースのアプローチSimPLe*3を上回った（表S1を参照）。
表S1：30のランダムなノーオペレーションスタートの個々のゲームのAtariでのMuZeroの評価

f:id:TadaoYamaoka:20191126231615p:plain:w200

  • 太字で強調されているのは各ゲームの最高の結果。
  • 各エピソードは、最大30分のゲーム時間（108kフレーム）に制限されている。
  • SimPLeは57ゲームのうち36ゲームでのみ評価され、利用できない結果は「-」で示されている。
  • 人間の正規化スコアは次のように計算される。s_{normalized}=\frac{s_{a g e n t}-s_{r a n d o m}}{s_{h u m a n}-s_{r a n d o m}}

サンプル効率を向上したバージョン

  • また、サンプルの効率を高めるために最適化されたMuZeroの2番目のバージョンも評価した。
  • 具体的には、最新のネットワークパラメータを使用してMCTSを再実行し、新しいターゲットを提供することにより、古い軌跡を再分析する（付録Hを参照）。
  • ゲームごとに2億フレームの経験を使用して、57のAtariゲームに適用した場合、MuZero Reanalyzeは以前の最先端のモデルフリーアプローチであるIMPALA*4、Rainbow*5およびLASER*6がそれぞれ192％、231％、431％であるのに対して、731％の正規化スコアの中央値を達成した 。
表1：MuZeroとAtariの以前のエージェントとの比較

f:id:TadaoYamaoka:20191225084442p:plain

  • 大規模（上）および小規模（下）のデータ設定で訓練されたエージェントと個別に比較する。
  • MuZero以外のすべてのエージェントは、モデルフリーRLテクニックを使用した。
  • 人間のテスターと比較した平均および中央値のスコアを示す。
  • 最良の結果は太字で強調されている。
  • MuZeroは、両方の設定で最先端(SOTA)を更新した。
  • 脚注a：ハイパーパラメータはゲームごとに調整された。

MuZeroでのモデルの役割を理解するための実験

  • MuZeroでのモデルの役割を理解するために、囲碁のボードゲームとMs.PacmanのAtariゲームに焦点を当てて、いくつかの実験も行った。

囲碁でのプランニングのスケーラビリティ

  • まず、囲碁の標準的なプランニングの問題で、プランニングのスケーラビリティをテストした（図3A）。
  • 完全なモデルを使用したAlphaZeroの探索のパフォーマンスと、学習したモデルを使用したMuZeroの探索のパフォーマンスを比較した。
  • 特に、完全に訓練されたAlphaZeroまたはMuZeroのMCTSを異なる思考時間で比較することにより評価した。
  • MuZeroは、モデルが訓練されたとき（思考時間約0.1秒、図S3Aも参照）よりもはるかに大きな探索（思考時間10秒まで）を行った場合でも、完全なモデルのパフォーマンスと一致した。
図3：囲碁（A）、57すべてのAtariゲーム（B）、Ms.Pacman（C-D）におけるMuZeroの評価

f:id:TadaoYamaoka:20191126233406p:plain

  • （A）囲碁での着手ごとの探索時間によるスケーリング、学習したモデルと正解シミュレータとの比較。
    • 両方のネットワークは、探索ごとに800回のシミュレーションで訓練され、探索ごとに0.1秒に相当する。
    • 驚くべきことに、学習したモデルは、訓練中に見られるよりも最大2桁長い探索まで拡張できる。
  • （B）Atariの最終的な人間の正規化された平均スコアと、探索ごとのシミュレーション数のスケーリング。
    • ネットワークは、探索ごとに50回のシミュレーションで訓練された。
    • 暗い線は平均スコアを示し、影付きの領域は25〜75および5〜95パーセンタイルを示す。
    • 学習したモデルのパフォーマンスは、探索ごとに最大100シミュレーションまで向上する。
    • さらに、訓練中よりもはるかに長い探索にスケーリングする場合でも、学習したモデルのパフォーマンスは安定したままで、わずかに低下するだけである。
    • これは、おそらく囲碁（A）よりもAtariのモデルの不正確さが大きいため、囲碁のスケーリングがはるかに優れていることとは対照的である。
  • （C）Ms.PacmanのMuZeroフレームワークでのMCTSベースの訓練とQ学習の比較（ネットワークのサイズと訓練量は一定）。
    • 最先端のQ学習アルゴリズムR2D2がベースラインとして示されている。
    • Q学習の実装は、R2D2と同じ最終スコアに達するが、MCTSベースの訓練と比較して、より遅く改善され、最終パフォーマンスは大幅に低下する。
  • （D）移動ごとに異なる数のシミュレーションで訓練された異なるネットワークだが、すべての移動ごとに50シミュレーションで評価された。
    • 移動ごとのシミュレーションを増やして訓練されたネットワークは改善が速くなり、アブレーション（B）と一致して、移動ごとのシミュレーションを多く使用すると方策の改善が大きくなる。
    • 驚くべきことに、Mu.Pacmanで可能な8つの行動すべてをカバーするのに十分な数よりも少ないシミュレーションで、MuZeroは効果的に学習できる。
図S3：MuZero評価（A-B）および方策改善アブレーション（C-D）の詳細

f:id:TadaoYamaoka:20191129000011p:plain

  • （A-B）図3A-Bの評価の学習モデルの探索木での評価の深さの分布。
    • ネットワークは、赤い線で示されているように、5つの仮想ステップで訓練された。
    • 濃い青色の線は、ルートからの深さの中央値を示し、濃い色の領域は25〜75パーセンタイル、薄い色の領域は5〜95パーセンタイルを示す。
  • （C）Ms.Pacmanの方策の改善 - 単一のネットワークが探索ごとに50回のシミュレーションで訓練され、生の方策ネットワークのargmaxに従ってプレイすることを含め、探索ごとに異なる数のシミュレーションで評価される。
    • 生の方策ネットワークを介した探索の方策改善効果は、訓練全体ではっきりと見える。
    • 探索ありと探索なしのパフォーマンスのこの一貫したギャップは、方策の改善に向けて継続的に更新することにより、MuZeroが活用する方策の改善を強調しており、最適な方策に向けて効率的に前進している。
  • （D）囲碁の方策の改善 - 単一のネットワークが探索ごとに800回のシミュレーションで訓練され、探索ごとに異なる数のシミュレーションで評価される。
    • 囲碁では、長い探索による強さの向上は、Mr.Pacmanよりもはるかに大きく、訓練全体を通じて持続し、AlphaGo Zero*7の以前の結果と一致している。
    • 直感的に予想されるように、これは、モデルの恩恵が正確なプランニングの分野で最大となることを示唆している。

Atariでのプランニングのスケーラビリティ

  • また、すべてのAtariゲームにわたるプランニングのスケーラビリティを調査した（図3Bを参照）。
  • 完全に訓練されたMuZeroを使用して、MCTSをさまざまな数のシミュレーションと比較した。
  • プランニングによる改善は、おそらくモデルの不正確さが大きいため、囲碁の場合よりも顕著ではない。
  • 探索時間でパフォーマンスはわずかに向上したが、100回程度のシミュレーションで停滞した。
  • MuZeroは1回のシミュレーション（つまり、方策ネットワークのみに従って移動を選択する場合）でも良好に機能し、訓練の終わりまでに、生の方策が探索の恩恵を内部化することを学習したことを示唆している（図S3Bも参照）。

モデルフリーアルゴリズムとの比較

  • 次に、モデルベースの学習アルゴリズムを、比較可能なモデルフリーの学習アルゴリズムに対してテストした（図3Cを参照）。
  • MuZeroの訓練目標（式1）をモデルフリーのQ学習目標（R2D2で使用）に置き換え、デュアル価値ヘッドと方策ヘッドをQ関数Q\left(\cdot | s_{t}\right)を表す単一のヘッドに置き換えた。
  • その後、探索を使用せずに新しいモデルを訓練および評価した。
  • Ms.Pacmanで評価した場合、モデルフリーのアルゴリズムはR2D2と同じ結果を達成したが、MuZeroよりも大幅に遅く学習し、はるかに低い最終スコアに収束した。
  • MuZeroの探索ベースの方策改善ステップは、Q学習で使用される高バイアス、高分散の目標よりも強力な学習信号を提供すると推測される。

訓練中の探索量のスケーラビリティ

  • MuZeroの学習アルゴリズムの性質をよりよく理解するために、MuZeroの訓練が訓練中に使用する探索の量に対してどのようにスケーリングするかを測定した。
  • 図3Dは、訓練中の動きごとに異なるシミュレーションカウントのMCTSを使用した際のMs.Pacmanのパフォーマンスを示している。
  • 驚くべきことに、以前の研究*8とは対照的に、MuZeroは1動作につき6回のシミュレーションでさえ、効果的な方策を学び、急速に改善した。

驚くべきことに、かつての作業とは対照的に、MuZeroは1動作につき6回（行動数より少ない）のシミュレーションでさえ、効果的な方策を学び、急速に改善した。

  • より多くのシミュレーションにより、パフォーマンスが大幅に向上した。
  • 各反復中の方策改善の分析については、図S3 CおよびDも参照。
感想

チェス、将棋では、AlphaZeroと同等の強さになっており、囲碁ではAlphaZeroを上回っています。
ただし、チェス、将棋では、AlphaZeroと同等になるのに1.0Mステップかかっているため、AlphaZero（0.7Mステップ）よりもより多くの訓練ステップが必要になるようです。ネットワークのブロック数は20から16と計算量は少なくなっています。
f:id:TadaoYamaoka:20191130223634p:plain

Atariでは、既存のモデルフリーのSOTAアルゴリズム（R2D2）を大幅に上回っています。

プランニング（MCTS）のスケーラビリティは、囲碁では思考時間に対してほぼ線形に伸びています。ただし、AlphaZeroの方がより線形に近く伸びておりスケーラビリティはAlphaZeroの方がよさそうです。

Atariではスケーラビリティは、囲碁ほど伸びていません。囲碁に比べてモデルの不正確さが大きいためと説明されています。
逆にAtariではシミュレーション回数が1回でもR2D2を上回る良好なパフォーマンスがでています。

Mr.Packmanでのモデルフリーアルゴリズムとの比較では、MuZeroが圧倒的に良い結果になっています。
今までモデルベースが使えなかった領域に適用した場合に、効果があるアルゴリズムと言えそうです。

訓練時の探索数については、Mr.Packmanでは訓練時の探索数を増やすほどより改善されるという結果がでています。
行動数よりも少ないシミュレーション回数でも学習するようです。

(続く)

*1:Human Level Control Through Deep Reinforcement Learning | DeepMind

*2:Recurrent Experience Replay in Distributed Reinforcement Learning | DeepMind

*3:[1903.00374] Model-Based Reinforcement Learning for Atari

*4:https://arxiv.org/abs/1802.01561

*5:https://arxiv.org/abs/1710.02298

*6:https://arxiv.org/abs/1909.11583

*7:Mastering the game of Go without human knowledge | Nature

*8:[1806.05780] Surprising Negative Results for Generative Adversarial Tree Search