TadaoYamaokaの開発日記

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

リバーシ(オセロ)で深層強化学習 その４（並列実行）

DQN リバーシ オセロ 強化学習 高速化

前回、DQNでリバーシ(オセロ)の強化学習を試して、ランダムより強くなることを確認した。
しかし、シングルステッドでシングルゲームを繰り返しているため1万イテレーションの実行に約14時間かかった。

方策勾配法のアルゴリズムであるA2Cでは、環境を並列実行して効率を高めるという工夫がされている。
AlphaStarでも並列対戦が実装されている。

私が作成しているdlshogiでもゲームを並列で実行することで、GPUの使用効率を高めている。

DQNでも、同様にゲームを並列実行することで、効率を高めることができる。
Pythonでは、GILの制約によりマルチスレッドにしても効率がそれほど上がらない問題があるので、シングルスレッドで複数ゲームを並列で実行して、方策の計算を複数ゲームをまとめてミニバッチで処理することでGPUによる並列化を行い高速化を行うことにする。

環境の並列実行

OpenAIのbaselinesでは、環境を並列実行のためにVecEnvクラスが実装されている。
そこで、VecEnvクラスを参考にして環境の並列処理を実装した。

baselinesではマルチプロセスで環境を並列化しているが、リバーシの1ステップの処理は、creversiではSIMDを使って高速化しているため、マルチプロセスのオーバヘッドの方が大きくなる。
そこで、シングルステッドで繰り返しで処理することにした。

DQNの並列処理の実装

学習の間隔

前回のシングルスレッド、シングルゲームでの実装では、エピソード終了の区切りで学習を行っていたが、環境を並列実行するとエピソードの終了のタイミングが環境ごと異なる。
そのため、エピソードの終了ではなく一定のステップごとに学習するようにする。
ただし、ステップ数の間隔は、前回の16エピソード終了ごととだいたい同じになるように調整した。

1ステップの間に、ミニバッチサイズ分のゲームが1ステップ進行するため、

OPTIMIZE_PER_STEPS = (60 * 16 + BATCH_SIZE - 1) // BATCH_SIZE

という式で、1ゲーム60手として16エピソードごとになるようにした。

ミニバッチサイズは256とした。

方策オフについて

前回はエピソード区切りで学習していたため、1ゲームの間に方策が変わることはない。
上記のように一定のステップ間隔で学習した場合、ゲームの途中で方策が変わることになる。

方策勾配法などの方策オンの学習では、ゲームの途中で方策を変えることはできない。
一方、DQNで使用されているQ学習は、方策オフ型であり、挙動方策と推定方策を分けることができる。
よって、ゲームの途中で方策を変更しても問題がない。

学習結果

DQNを並列実行して、1万イテレーション学習した結果は以下のようになった。

損失

損失のグラフは以下のようになった。
f:id:TadaoYamaoka:20191208213014p:plain

3000イテレーションくらいまでは、前回のシングルゲームと比べて、損失が上昇している。
この違いは、並列実行することで、ミニバッチサイズ分のゲームが同じ方策を使って経験データを蓄積するため、序盤のランダムに近い方策によって生成されたデータをより多く学習するためと思われる。
3000イテレーション以降は、比較的安定して学習できている。

強さ

ランダムと1000局対局した結果は、833勝152敗15分となった。
信頼区間95%の勝率は、86.7～82.2%となった。

前回のシングルゲームの64.9～58.8%と比べて、高くなっている。
学習間隔の計算で小数点の繰り上げを行っているので、生成した局面は多くなっているのでそのままは比較できないが、実行時間に対して効率よく学習できている。

学習時間

並列実行することで、前回は1万イテレーションで、約14時間かかったが、約1時間30分に短縮された。

まとめ

環境を並列実行することで、DQNの学習を効率化できた。
マルチスレッドやマルチプロセスにしないでも、シングルスレッドで環境を並列化することでGPUを効率的に利用できる。

次回は、強化学習の他のアルゴリズムを試していきたい。

ソース

DQNの並列実行のソースはこちら。
creversi_gym/dqn_parallel.py at master · TadaoYamaoka/creversi_gym · GitHub

リバーシ(オセロ)で深層強化学習 その３（DQN）

リバーシ 強化学習 DQN オセロ

前回、DQNのネットワークを教師ありでQ学習で学習した。
今回は、DQNを強化学習で学習する。

実装するアルゴリズムは、Nature に掲載された論文「Human-level control through deep reinforcement learning」に基づく。
DeepMindによる公式の実装は、TensorFlowもPyTorchもない時期なので、LuaJITとTorch 7.0で実装されている。

今ではTensorFlowかPyTorchで実装する方がよいので、分かりやすいチュートリアルが提供されているPyTorchの実装を参考にすることにした。

OpenAI Gymについて

PyTorchのチュートリアルは、OpenAI GymのCartPoleをDQNで学習するサンプルになっている。
強化学習は、環境とエージェントの相互作用で学習を行うが、環境とエージェントのインターフェースを統一することで、それぞれ差し替えて実験するのが容易になる。
そのために、OpenAIがインターフェースを定義して、CartPoleやその他の強化学習の研究で使用される代表的な環境を提供している。

リバーシのOpenAI Gymインターフェース

残念ながら、OpenAIではリバーシの環境は提供されていない。
そこで、リバーシのOpenAI Gymインターフェースを、creversiに実装した。

リバーシに合わせた変更

PyTorchのチュートリアルは、OpenAI GymのCartPole向けになっているので、リバーシに合わせて変更が必要になる。

エピソード完了後に学習

CartPoleでは、ステップごとに報酬が得られるが、リバーシではゲームの終了まで報酬が得られない。
リバーシでもステップごとに学習を行うことも可能だが、効率が悪いためエピソード終了の区切りで学習を行うことにする。
1回ごとに学習するよりも、数エピソードごとに学習した方が学習が安定するため、16エピソードごとに学習することした。

DQNでは、方策に使用するネットワーク(policy_net)と、価値を推定する際の使用するネットワーク(target_net)が分かれている。
policy_netは毎回学習し、target_netは一定間隔ごとにpolicy_netからパラメータがコピーされる。

CartPoleのサンプルでは、10ステップごとにコピーを行っているが、64エピソードごととした。

学習間隔とpolicy_netからtarget_netへのコピーの間隔は、チューニングが必要なハイパーパラメータになるが、今回は適当に決めている。

ミニマックスを考慮した行動価値

DQNで使用されるQ学習は、1ステップ後の行動価値の最大値を使用するが、リバーシでは1ステップ後は相手の手番のため、行動価値の符号を反転する必要がある。

割引率

DQNでは、1ステップ後の行動価値に対して割引を使用するが、ボードゲームでは割引を使用しないで学習することが多い。
AlphaZeroでも、終端の報酬を割引なしで学習している。
そのため、割引率は高めの0.99とした。

εグリーディー

DQNの方策には、εグリーディー戦略が用いられる。
基本は、policy_netで行動価値が最大となる行動が選択されるが、一定の割合εでランダムに行動が選択される。
強化学習では、すでに価値が高いとわかった行動を優先して探索するが、まだ探索していない行動の方がより価値の高い可能性があるため、未知の行動の探索も必要である。
εグリーディー戦略では、一定の割合εでランダムな行動を選択すること、探索と活用のバランスをとる。

εは、はじめに高めで、徐々に小さくしていくと良いことが知られている。
チュートリアルでは、
\displaystyle \varepsilon_{end} + (\varepsilon_{start} - \varepsilon_{end}) \cdot \exp(-\text{steps_done} / \varepsilon_{decay})
という式が使用されている。
ここで、\varepsilon_{start}、\varepsilon_{end}、\varepsilon_{decay}は定数で、それぞれ
\varepsilon_{start} = 0.9 \\ \varepsilon_{end} = 0.05 \\ \varepsilon_{decay} = 200
という値が使用されている。

グラフにすると、

のようになり、\varepsilon_{start}から徐々に小さくなり、\varepsilon_{end}で一定になる。
\varepsilon_{decay}は、小さくする速度を制御している。

リバーシでは、ステップ数をエピソード数に置き換えて、\varepsilon_{start}と\varepsilon_{end}は、同じ値を使用し、\varepsilon_{decay}は2000とした。

学習結果

教師ありのQ学習では、1万ステップ学習してもランダムよりも強くならなかった。
そのため、最低でも1万ステップ以上は学習する必要があると思われる。
そこで、一旦1万ステップ(16万エピソード)の学習を試すことにした。

損失

損失のグラフは以下のようになった。

はじめ順調に下がった後、上昇してまた下がっている。
まったく学習できていないわけでもなさそうである。

強さ

ランダムと1000局対局して強さを測定した。
597勝368敗35分という結果になった。
信頼区間95%の勝率は、64.9～58.8%で、ランダムより有意に強くなっている。

学習時間

16万エピソードの学習にはGeForce 2080Tiを使用して、約14時間かかった。

まとめ

リバーシで、DQNを用いて強化学習することで、ランダムより強くできることが確認できた。

リバーシは、ルールがシンプルで60手で必ず勝負がつくので強化学習の勉強題材としては良いのではないかと思う。
将棋ではDQNがまった学習できなかったので、とりあえずランダムより強くなるという結果がでて良かった。

シングルスレッドでシングルゲームを繰り返しているので、ゲームを並列実行することで学習時間は短くできるはずである。
他のアルゴリズムを試す前に、並列実行を実装したい。

その後、DDQNなど他のアルゴリズムも試したい。
あと、GUIソフトと連携させて人間とも対局できるように、プロトコルも実装するつもりである。

ソース

実装したDQNのソースは、こちら。
creversi_gym/dqn.py at master · TadaoYamaoka/creversi_gym · GitHub

MuZeroの論文を読む その５（AlphaZeroとの比較）

MuZero

付録A AlphaZeroとの比較

  • MuZeroは、AlphaGo Zero*1やAlphaZero*2よりも一般的な設定向けに設計されている。
AlphaZeroのプランニング
  • AlphaGo ZeroとAlphaZeroでは、プランニングプロセスは2つの別個のコンポーネントを使用する。
  • シミュレーターは、ゲームのルールを実装する。これは、探索木を走査しながらゲームの状態を更新するために使用される。
  • また、ニューラルネットワークは、シミュレータによって生成された局面の対応する方策と価値を合わせて予測する（図1 Aを参照）。

f:id:TadaoYamaoka:20191121214604p:plain

AlphaZeroとの比較の詳細
  • 具体的には、AlphaGo ZeroおよびAlphaZeroは、（1）探索木の状態遷移、（2）探索木の各ノードで利用可能な行動、（3）探索木内のエピソード終了の3つの場所でゲームのルールの知識を使用する 。
  • MuZeroでは、これらのすべてが、ニューラルネットワークによって学習された単一の暗黙的なモデルの使用に置き換えられた（図1 Bを参照）。
  • 1) 状態遷移
    • AlphaZeroは、真のダイナミクスプロセスの完璧なシミュレータにアクセスできた。
    • 対照的に、MuZeroは探索内で学習したダイナミクスモデルを採用している。
    • このモデルでは、木内の各ノードは対応する隠れ状態で表される。
    • 隠れ状態s_{k-1}とアクションa_kをモデルに提供することにより、探索アルゴリズムは新しいノードs_{k} = g(s_{k-1}, a_k)に遷移できる。
  • 2) 利用可能な行動
    • AlphaZeroは、シミュレーターから取得した一連の合法な行動を使用して、探索木のあらゆる場所でネットワークによって生成された事前分布をマスクした。
    • MuZeroは、環境のクエリが可能な探索木のルートでのみ合法な行動をマスクしますが、探索木内ではマスキングを実行しない。
    • これは、ネットワークが訓練された軌跡で決して発生しない行動を予測しないことを急速に学習するために可能である。
  • 3) 終端ノード
    • AlphaZeroは、終端の状態を表すノードで探索を停止し、ネットワークによって生成された価値の代わりに、シミュレータによって提供された終端の価値を使用した。
    • MuZeroは終端ノードに特別な処理を行わず、ネットワークによって予測された価値を常に使用する。
    • 木内で、探索は終端ノードを通過できる。この場合、ネットワークは常に同じ価値を予測することが期待される。
    • これは、訓練中に終端状態を吸収状態として扱うことで実現されます。
AlphaZeroより一般的な設定
  • さらに、MuZeroは一般的な強化学習設定（任意の大きさの割引された中間報酬を持つシングルエージェントドメイン）で動作するように設計されている。
  • 対照的に、AlphaGo ZeroとAlphaZeroは、±1の割引なしの終端報酬で2プレイヤーゲームで動作するように設計されている。
感想

AlphaZeroではMCTSのシミュレーションでは探索中の局面で着手を合法手でマスキングするためにゲームのルールを使用していましたが、MuZeroではマスキングを行わないことが述べられています。
ニューラルネットワークを訓練することで、常に合法手が出力されることを期待しています。

また、AlphaZeroでは探索中にゲームの終了をチェックして、ゲームの結果を価値としてバックアップを行っていましたが、MuZeroでは終了のチェックは行わず常にネットワークが予測する価値を使用しています。
この仕組みだと探索中にゲームの終了を認識できないので、終端状態を通過して探索を続けてしまう問題があります。
対策として、訓練中に終了状態からは同じ終了状態に遷移するように訓練されています。マルコフ連鎖の用語で吸収状態(absorbing states)というようです。

将棋では、詰みの状態はいくら駒損しても詰めばよいため序盤中盤の局面とは性質が違うため、ゲームルールを使用した探索の支援なしにニューラルネットワークのみで学習するのは難しそうですが、MuZeroで学習できているのはすごいことのように思います。

MuZeroの一般性については、AlphaZeroは中間報酬のない2人ボードゲームに特化していましたが、中間報酬と割引ありシングルエージェントに適用できると述べられています。
それによって、AtariにもAlphaZeroライクな探索が導入可能になっています。

(続く)

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

*2:A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play | DeepMind

リバーシ(オセロ)で深層強化学習 その２（教師ありQ学習）

リバーシ 強化学習

前回、オセロの棋譜の終端の報酬を使用して(TD(1))、教師ありで学習することでランダムより強くなることを確認した。

今回は、教師ありでQ学習を試す。

Q学習

Q学習の学習則は以下の式で表される。
\displaystyle \delta=Q(s, a)-\left(r+\gamma \max _{a} Q\left(s^{\prime}, a\right)\right)

rは、遷移に対応する即時報酬で、リバーシ(オセロ)の場合、終端以外では0になる。
\max _{a} Q\left(s^{\prime}, a\right)は、1ステップ先の局面での行動価値が最大となる手の行動価値である。

よって、学習の開始時は、ほとんどの局面で、ランダムで初期化されたニューラルネットワークの出力のうち、偶然最大になった値を教師として学習することになる。
学習が進むにつれ、徐々に終端の報酬が序盤の局面にも伝播していく。

棋譜の偏り

前回使用した棋譜を調べたところ、引き分けのゲームが8割以上含まれていた。
GGSの棋譜だけの傾向かもしれないが、オセロは引き分けが多いゲームのようだ。
そのまま使用すると終端の報酬の多くが0になってしまい学習が進まないことが予想される。
そこで、引き分けのゲームが1割以下になるように間引いて使用することにした。

ミニマックス対応

1ステップ後の行動価値は、相手局面になるため、Q\left(s^{\prime}, a\right)は、ニューラルネットワークの出力の符号を反転する必要がある。

パス対応

前回の終端の報酬を使った学習では、パスした局面は除外して学習を行った。
そのため、ニューラルネットワークの出力でもパスは考慮していなかった。

Q学習の場合、1ステップ後がパスとなる局面を考慮する必要があるため、ニューラルネットワークの出力にパスを加えた。
そのため、出力層は1×1の畳み込みから、全結合層に変更した。

学習結果

1万ステップ学習した結果は以下の通り。
f:id:TadaoYamaoka:20191205220744p:plain
前回に比べて損失の値の桁が一つ小さい。

強さの測定

ランダムとの対局した結果は、453勝500敗47分となった。
1万ステップではほとんど学習できていない。

終端の報酬で学習した場合との比較

同じネットワーク構成と教師局面で、終端の報酬で学習した場合は、同じ1万ステップで675勝281敗44分となった。
明らかに、Q学習の方が学習速度が遅い。

10万ステップ学習した結果

ステップ数を増やせば学習できるか確認するため、10万ステップ学習した。
f:id:TadaoYamaoka:20191205221328p:plain
前回は途中で横ばいになったが、Q学習の場合横ばいにならずに学習が進んでいる。

ランダムとの対局結果は、757勝214敗29分となった。
終端の報酬で10万ステップ学習した場合は、639勝330敗31分となった。
学習が進むと、Q学習の方が逆転して強くなっている。

まとめ

DQNのネットワークをQ学習でも学習できることが確認できた。
また、学習の初期は終端の報酬を使用した方が学習が早く進み、学習が進むと、終端の報酬よりQ学習の方がパフォーマンスが良くなることがわかった。

次は、強化学習でDQNを学習させてみたい。


学習に使用したソースはこちら。
creversi_gym/train_from_training_data.py at master · TadaoYamaoka/creversi_gym · GitHub
creversiもちょくちょく改良しています。

MuZeroの論文を読む その４（結論）

MuZero

本文の残り、結論の部分です。

結論

  • 人工知能のブレークスルーの多くは、高パフォーマンスプランニングまたはモデルフリー強化学習方法に基づいている。
  • この論文では、両方のアプローチの利点を組み合わせた方法を紹介した。
  • 私たちのアルゴリズムMuZeroは、論理的に複雑なドメイン（チェスや囲碁などのボードゲーム）での高パフォーマンスプランニングアルゴリズムの超人的なパフォーマンスと、視覚的に複雑なドメイン（Atariゲーム）で最先端のモデルフリーRLアルゴリズムを上回った。
  • 重要なのは、私たちの方法はゲームのルールや環境のダイナミクスに関する知識を必要とせず、強力な学習およびプランニング方法を完璧なシミュレーターが存在しない現実世界の多くのドメインに適用する可能性を秘めていることである。
感想

結論では、ゲームのルールを必要としないで（環境から返されるデータだけで）学習できるという点が強調されています。
以前のAlphaZeroでは、MCTSのシミュレーションでゲームのルールを使用していましたが、環境（ボードゲームの場合は遷移確率）をニューラルネットワークでモデル化することで、ゲームのルールが不要となっています。
シミュレーションの結果を使って実際に着手する際は合法手のチェックは必要なので、まったくルールを使っていないかというと微妙ですが。

読み始める前は私が開発しているdlshogiに応用できるかもという期待はありましたが、チェスと将棋ではパフォーマンスはAlphaZeroと同程度で、AlphaZeroより学習ステップ数が増えているので、そのまま取り入れるメリットはなさそう。
ただしAlphaZeroのメソッドと併用するなど応用の可能性はありそうなので、技術的な興味もあるので一度実装してみたいと思っています。

次回は、付録を読んでいきます。

AlphaStarの論文を読む その１３（分析、AlphaStarの一般性）

AlphaStar 強化学習

分析

エージェントセット

  • 検証エージェント：メインエージェントのみを使用し、エクスプロイターを使用せずに訓練された17の戦略セットに対するリーグの堅牢性を検証し、zを手で精選された興味深い戦略セット（例：キャノンラッシュや初期飛行ユニット）に修正した。
  • アブレーションテストエージェント：アブレーションテストエージェントには、検証エージェント、および完全なリーグトレーニングによって作成された最初の（つまり弱い）20のメインおよび20のリーグエクスプロイトプロトスエージェントが含まれる。
  • 固定相手：RLアルゴリズムを評価するために、リーグトレーニングによって作成された最初の10人のリーグエクスプロイトプロトスエージェントで構成される均一な混合戦略に対する最良の応答を計算した。

図で使用されるメトリック

  • Eloレーティング：リーグの内部Eloレーティングを計算するために、組み込みのボットを追加し、それを使用して次のモデルでEloを推定した。


\displaystyle \mathbb{P}[\mathrm{r}_{1} \text { beats } \mathrm{r}_{2}]=\frac{1}{1+e^{-\left(\mathrm{r}_{1}-\mathrm{r}_{2}\right) / 400}} \approx \Phi\left(\frac{\mathrm{r}_{1}-\mathrm{r}_{2}}{400}\right)

  • ここで、\mathrm{r}_{1}と\mathrm{r}_{2}は両方のプレイヤーのEloレーティングである。
  • Eloレーティングには固有の絶対スケールがないため、組み込みのEliteボットのレーティングを0に設定することにより、Eloレーティングを接地する。
相対集団パフォーマンス
  • 相対集団パフォーマンス（Relative Population Performance; RPP）は、2つの集団(population)がナッシュ均衡に達した後の2つの集団間のメタゲームの予想される結果である*1。
  • リーグAとBの、それぞれサイズNとMのすべてのエージェント間の利得行列が与えられた場合、P_{A B} \in[0,1]^{N \times M}：


\displaystyle \operatorname{RPP}\left(P_{A B}\right)=\operatorname{Nash}\left(P_{A B}\right)^{T} P_{A B} \operatorname{Nash}\left(P_{B A}\right)

  • ここで、\operatorname{Nash}(X) \in[0,1]^{K}は、サイズKのリーグXにおけるナッシュ均衡で各エージェントをプレイするために割り当てられた確率のベクトルである。
  • RPPが高いということは、リーグAがBからのエージェントを活用できる混合戦略を形成できるエージェントで構成されていることを意味する。

AlphaStarの一般性

ニューラルネットワークアーキテクチャコンポーネント
行動空間の定義
  • AlphaStarの行動空間は、型指定された引数を持つ関数のセットとして定義される。
  • 同様のAPIを定義するドメインはすべて、複雑で構造化された行動空間の同じ分解に取り組むことができ、その結合確率はチェーンルールによって分解される（たとえば、言語モデリング*2や定理証明に似ている）。
模倣学習
  • AlphaStarでの模倣学習には、効果的な人間による大量のデモンストレーションが必要であるため、このようなデモンストレーションセットを提供するドメインにのみ適用できる。
  • 潜在変数zを使用して探索を誘導することはStarCraftに固有ではないが、統計の特定の選択にはドメインの知識が必要だった。
  • 特に、StarCraftで序盤とユニットをエンコードするためにzを選択した。
  • 擬似報酬は、編集距離やハミング距離など、これらの統計の適切な距離メトリックに基づいている。
強化学習アルゴリズム
  • AlphaStarの基礎となる強化学習アルゴリズムは、どのRL環境にも適用できる。
  • また、より低い分散のベースラインと新しいコンポーネント（例えば、ハイブリッド方策オフ学習、UPGO、模倣ポリシーに向けた蒸留など）のために敵の観測を使用することも広く適用できる。
マルチエージェントトレーニング
  • 最後に、メインエージェントを強化することを目的とするさまざまな種類のエクスプロイターを使用した新しいマルチエージェントトレーニング体制を提案する。
  • 優先順位付きFSPとともに、これらはすべてマルチプレイヤードメインに適用可能な汎用技術である。

コードおよびデータの可用性と声明

プロフェッショナルプレーヤーの声明

  • 次の引用は、StarCraft IIプロプレイヤーであるDario “TLO” Wünsch（チームの一員であり、この論文の著者でもある）によるもので、インターフェイスと制限について説明している。
Dario “TLO” Wünschの声明
  • AlphaStarに設定されている制限は、1月の最初のショーマッチとは非常に異なると感じる。
    • AlphaStarには優れた正確な制御機能があるが、超人間的な感覚はない。
    • 人間が理論的に達成できないレベルではない。
    • 人間よりもいくつかの面で優れており、他の面でも悪化しているが、もちろんAlphaStarと人間のプレイヤーの間には避けられない違いがある。
  • DeepMindのシステムが人間のプレイヤーよりも不公平に優位にならないようにするために、AlphaStarチームに相談できることを嬉しく思った。
  • 全体として、StarCraftの「本物の」ゲームをプレイしており、非現実的な機能を備えているためにバランスが完全に失われておらず、非常に公平に感じる。
  • カメラの表示が制限されているため、マルチタスクを実行するときに常にすべてを同時に捕捉できるとは限らないため、その側面も非常に公平で人間らしく感じられる。

リプレイデータ

  • AlphaStarがオンラインでプレイしたすべてのゲームはファイルreplays.zip（Supplementary Data Replays）にあり、Battle.netの実験の生データはbnet.json（Supplementary Data Battle.net）にある。

コード

感想

全体を読んでみて、個人的にポイントと思ったのは以下の点です。

  • 不完全情報ゲームのサイクル問題を回避するためリーグマッチによるマルチエージェントで学習している
  • リーグの対戦相手の選択を優先順位付きFSPで効率化している
  • 複雑な長期戦略を強化学習では学習できない
  • そのため人間のリプレイを利用する
  • ニューラルネットワークはLSTMを使用する
  • 入力は、トランスフォーマーでユニットを埋め込み表現にしている
  • 埋め込み表現にしたユニットを、畳み込みにスキャッター接続することで空間情報を保持して入力する
  • 行動の出力は、複数のアクション引数をネットワーク構成で表現している
  • 引数の出力に応じて、ポインターネットワークやアテンションが使用されている
  • 強化学習アルゴリズムは、アクタークリティックがベース
  • 方策の学習にはリプレイバッファを使用してV-Traceで方策オフで学習する
  • 加えてUPGOで自己模倣学習を行う
  • 価値の学習はTD(λ)を使用し方策オフの補正は行わない
  • 対戦条件は、操作頻度やカメラ操作を人間の条件に近づけて公平にしている

AlphaStarの論文を読む - TadaoYamaokaの開発日記
AlphaStarの論文を読む その２ - TadaoYamaokaの開発日記
AlphaStarの論文を読む その３ - TadaoYamaokaの開発日記
AlphaStarの論文を読む その４ - TadaoYamaokaの開発日記
AlphaStarの論文を読む その５（アーキテクチャ） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その６（アーキテクチャその２） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その７（アーキテクチャその３） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その８（教師あり学習、強化学習） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その９（マルチエージェント学習） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その１０（リーグ構成） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その１１（インフラ） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その１２（評価） - TadaoYamaokaの開発日記
AlphaStarの論文を読む その１３（分析、AlphaStarの一般性） - TadaoYamaokaの開発日記

*1:[1901.08106] Open-ended Learning in Symmetric Zero-sum Games

*2:https://www.fit.vutbr.cz/research/groups/speech/publi/2010/mikolov_interspeech2010_IS100722.pdf

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