論文読み：Retrospective Analysis of the 2019 MineRL Competition on Sample Efficient Reinforcement Learning

ちょっと軽めのArxivの論文を読もうと思い、MineRLのコンペについての論文を読んでみました。

はじめに

2019年のMineRL Competition の解説論文。
ちなみに、2019年のTopのチームの学習結果の動画のはこちら

論文・参考サイトへのリンク

Retrospective Analysis of the 2019 MineRL Competition on
Sample Efficient Reinforcement Learning

著者

• Stephanie Milani [e-mail] Machine Learning Department, Carnegie Mellon University
• Nicholay Topin [e-mail] Machine Learning Department, Carnegie Mellon University
• Brandon Houghton∗ [e-mail] OpenAI
• William H. Guss [e-mail] OpenAI and Machine Learning Department, Carnegie Mellon University
• Sharada P. Mohanty [e-mail] AIcrowd
• Keisuke Nakata [e-mail] Preferred Networks
• Oriol Vinyals [e-mail] DeepMind
• Noboru Sean Kuno [e-mail] Microsoft Research
• Editors: Hugo Jair Escalante and Raia Hadsell

注：と記載したところは、このQiita記事の筆者である @ikeyasu のコメントです
以下、できるだけ論文の流れに沿ってまとめます。
図は、全て元論文からの引用です。
訳は Google Translate や DeepL にお手伝いして頂きました。

Abstract

サンプル効率の良い強化学習の方向性の研究を促進するために、第33回Neural Information Processing Systems Conference on Neural Information Processing Systems (NeurIPS 2019)において、「Sample Efficient Reinforcement Learning Using Human Priors on MineRL Competition on Sample Efficient Reinforcement Learning Using Human Priors」を開催された。
ここでは、このコンペティションの第一の目的は、複雑で階層的で疎な環境を解くのに必要なサンプル数を減らすために、強化学習と並行して人間のデモを利用するアルゴリズムの開発を促進することであった。
このコンペティションについて、主要な課題、コンペティションのデザイン、参加者に提供したリソースの概要を説明すする。
また、それぞれが深層強化学習や模倣学習を利用している上位のソリューションの概要を説明する。また、組織的な決定が競争に与えた影響と、今後の改善の方向性についても議論する。

1. Introduction

AlphaStar（Vinyalsら、2019年）、AlphaZero（Silverら、2018年）、およびOpenAI Fiveのような最近の、人工知能（AI）の有名な成功の多くは、深層強化学習（DRL）を使用して、人間または超人レベルの性能を達成している。

これまでのところ、最先端の状態への改善は、増大し続ける計算能力を使用してきた。

この計算量の増加は、環境サンプルあたりの計算量の増加によるものもあるが、主に学習アルゴリズムの学習に必要な環境サンプル数の増加によるものである。

このような計算量の増加は、システムの改良はおろか、AIコミュニティの一部がこれらの結果を再現することができなくなっていることを意味する。

環境とサンプルの複雑さを軽減し、ひいてはメソッドにアクセスしやすくするためのよく知られた方法の1つは、人間のデモンストレーションと事前動作(prior over desired behavior)を利用して、望ましい動作を実現することである。(Pfeiffer et al., 2018; Dubey et al., 2018; Zhang et al., 2019)。

強化学習コンペティション

私たちの知る限りでは、これまでのコンペティションでは、模倣学習（およびより一般的にはデモからの学習）をRLと一緒に使用することに明示的に焦点を当てたものはなかった。
これまでのほとんどのRL競技会(Kidziski et al., 2018; Nichol et al., 2018; Perez-Liebana et al., 2018; Juliani et al., 2019)では、与えられたドメインでの性能向上に焦点を当てており、幅広いドメインセットで性能を発揮できるロバストなアルゴリズムの開発には焦点を当てていなかった。その結果、受賞した提出物は、多くの場合、手作業で設計された特徴を必要とし、トレーニングと開発のために大量の計算リソースを使用していた。

3. Competition Overview

コンペティションの概要を説明する。セクション3.1では主要なタスクと環境について述べる．セクション3.2では、競技会の構成を説明する。セクション3.3では、参加者に提供したリソースについて説明する。

3.1. Task

コンペ参加者は、ObtainDiamond 環境を解決することを課題とした。
この環境を解くためには、Minecraftの複雑なアイテム階層をナビゲートしてダイヤモンドを得るために、具現化されたエージェントを制御する必要がある。

このタスクを解く際に、学習アルゴリズムは、具現化されたMinecraftエージェントの視点からの64x64ピクセルのObservationと、エージェントが所有しているダイヤモンドを得るために必要な各アイテムからなる離散的な観測のセットに直接アクセスすることができる。

アクション空間は、連続的な視野調整（旋回とピッチング）、二値移動コマンド（左/右、前進/後退）、およびブロックの配置、アイテムのクラフト、アイテムの錬成、および敵の採掘/打撃のための離散的なアクションの直交積である。

エージェントはダイヤモンドを手に入れるというフルタスクを完了すると報酬を受け取ることができる。
ダイヤモンドを手に入れるというフルタスクは、難易度の高い一連の前提条件のサブタスクに分解することができる。
エージェントは連続した各サブタスクを初めて達成した時にも報酬を受け取る。
エージェントは、前のサブタスクを達成したときの２倍の報酬を受け取りる（報酬は１から始まる)。このルールの例外は、ダイヤモンドを手に入れることで完全なObtainDiamondタスクを達成することである：最後のタスクを達成することは、前のサブタスクを達成することの4倍の価値がある。

3.2. Competition Design

競技は2つのラウンドに分けて行われた。
第1ラウンドでは、最大6名の参加者で構成されるチームがエージェントを訓練し、訓練されたモデルを評価用に提出してリーダーボードのランクを決定した。
このラウンドでは、各チームの提出物を合計25件に制限した。ラウンド1の終わりに、各チームはソースコードを提出した。各提出物には、その提出物が100エピソードにわたって達成した平均的な報酬からなるスコアが与えられた。その後、各チームの上位の提出物は、ルールを遵守しているかどうかを確認するために、ルール委員会によって審査された。最もスコアが高く、ルールに準拠した作品を提出した13チームがラウンド2に進んだ。これらのチームを招待して、NeurIPS 2019 コンペのワークショップで作品を発表してもらった。Microsoft Researchの支援を受けて、各チームに1200ドルの渡航費を支給し、カンファレンスに参加していただいた。

ラウンド2では、各チームは、ホールドアウト(held-out)されたテスト環境上でランダムな重みから訓練する学習手順を5つまで提出することができた。
我々は、各提出物をAzure NC6とNC12インスタンスを使用して、800万サンプルの厳密な環境ステップバジェット（注：a strict environment step budget。ステップ800万回を厳密に守るという事？）で6日間、独立して学習した。
一般化可能性(注：generalizability。こっこでは提出物の手法が一般的に適用できるかという意)とルールの遵守を促進するために、最終ラウンドで提出されたソリューションを以下の方法で再訓練した。
1) 混乱させた(perturbed)アクション空間、
2) 全く新しい未見のテクスチャパック（図1(c)に図示）
を使用して、最終ラウンドで提出されたソリューションを再調整した。
チームには検証用のテクスチャパック6（図1(b)）を提供し、学習手順を提出する前に、自分たちのアプ ローチが未見の環境でも一般化できるかどうかを確認できるようにした。
最終的なランキングは、各チームの最高得点の提出物に基づいて決定された。

訓練学習手順のユニークなパラダイムを考慮して、サンプル効率と一般化可能性を促進するために厳格なルールを設定し、参加者が事前に訓練されたモデルをロードしないようにした。
サンプル効率の制約は、800万フレーム（約110時間のゲーム内インタラクション）という厳しい環境サンプル制限を設定し、計算時間を144時間の実時間（Wall clock time）に制限することで実施した。
フレームスキップを許可したが、スキップされた各フレームはサンプルバジェットにカウントされる。
参加者はエージェントのObservationを自由に形作ることができましたが、それをポリシーに直接エンコードすることはできませんでした。例として、収集されたログの数に基づいてサブポリシーを切り替えることは許可されませんでした。参加者が事前に訓練されたモデルを参加者の提出物に含めることを避けるために、第2ラウンドでは、提出されたコードリポジトリ内の4MBを超えるファイルはプログラム上削除されました。競争のパラダイムのより詳細な議論は、以前の研究(Houghton et al., 2019)にあります。

両ラウンドとも、参加者はAIcrowd-repo2dockerと互換性のあるスタンドアロンのリポジトリとしてコードを提出した。
これらのリポジトリにはコード、訓練モデル、ランタイム仕様が含まれており、サブミッションから一貫性のあるDockerイメージを構築することがでた。
これらのイメージは、ラウンド固有のポリシーを尊重しながら、カスタムKubernetesクラスタ上でオーケストレーションされた。参加者が提出した悪意のあるコードによる情報漏洩を防ぐために、完全にネットワークから隔離された状態で提出されたことを評価した。

3.3. Resources

ObtainDiamondタスクに加えて、ObtainDiamondを解くのに役立つと思われる補助タスクをいくつか作成した。
これらのタスクは、ジム環境としてパーティシパントに提供した（Brockman et al. さらに、私たちは、広範なドキュメント、スターターコード、提出手順の説明、Microsoft Azureのクイックスタートテンプレート、再訓練中の訓練手順を検証するために使用したDockerイメージからなる包括的なスターターパック8を参加者に提供した。
参加者には、参加者がエージェントを訓練するために使用できる人間のデモンストレーションの大規模なデータセット（Guss*ら、2019年）を渡しました。Preferred Networksは、ChainerRLで実装された広範なベースライン10を提供した(Fujita et al., 2019)。
参加者は、これらのベースラインを提出物に組み込むことができた。これらのベースラインには、行動クローニング、デモからの深いQ-learning from demonstration（DQfD）（Hesterら、2018）、Rainbow（Hesselら、2018）、generative adversarial inverse RL（GAIL）（Ho and Ermon、2016）、およびproximal policy optimization（PPO）（Schulmanら、2017）が含まれていた。

AIcrowd11は、参加者が大会に登録したり、主催者や他の参加者に質問をしたり、参加者の進捗状況を確認したりするための統一されたインターフェースを提供した。また、参加者とのより非公式なコミュニケーションのために、公開のDiscordサーバーを作成した。
寛大なスポンサーであるMicrosoft Azureを通じて、コンペに参加するのに必要なコンピュートパワーへのアクセスが不足していると自認している50人に、それぞれ500ドルのコンピューターリソース(compute grants)をMicrsoft Azureクレジットで提供した。さらに、Microsoft Azureのおかげで、第1ラウンドのトップチームには、第2ラウンドでの実験のために1500USDのAzureクレジットを提供した。

4. Outcomes for Participants

本コンテストの参加者が提出した投稿を定量的・定性的に分析した。4.1 節では、応募作品の定量的な情報を提供する。4.2 節では、最終ラウンドで上位 9 チームが採用したアプローチをまとめた。第4.3節では、本大会で授与された特別賞について述べる。

4.1. Submission Performance Overview

ラウンド1では540件以上の応募があり、25チームが提供されたベースラインを大幅に上回る結果となった。
表1は、ラウンド2のエージェントはホールドアウトテスト環境で訓練されているにもかかわらず、ラウンド2の上位3チームがラウンド1の上位3チームを平均して上回っていることを示しています（平均値：それぞれ48.27と44.33）。意外かもしれませんが、ラウンド1のスコアは、ラウンド2のスコア（それぞれ25.84と17.37）よりも平均値が高く（31.77）、標準偏差が低く（10.22）なっています。また、ラウンド1の得点は、ラウンド2の得点(53.74)に比べて範囲が狭く(31.30)なっている。図 2 は、Round2 の評価エピソードにわたる項目スコアの最大値を示したものである。ダイヤモンドを獲得したチームはなかったが、トップチームはダイヤモンドを獲得するための最後の前提条件となる項目を獲得した。

4.2. Summary of Top Nine Solutions

上位4チームは、Minecraftの階層性を利用して、何らかの形式の階層型RLを使用していた。すべてのチームは、環境の複雑さを管理するために、何らかの形のアクション削減（人間の専門家がほとんど実行しないアクションを削除するなど）を使用していた。ほとんどのチームが人間のデータを活用してアルゴリズムのサンプル効率を向上させた。

トップチームであるCDSは，別個のデモ再生バッファからエキスパートのデモをサンプリングするために適応比を使用する忘却を伴う階層的なディープQネットワークを使用しました(Skrynnik et al., 2019)．第2位のチームmc_rlは，環境との相互作用を伴わない人間のデモンストレーションから階層的なポリシーを完全に学習した．第3位のチームであるi4DSは、デモンストレーションを使用して階層的RLアルゴリズムをブートストラップし、人間のデータを効果的に使用して、記録された人間の行動をオブザベーションから予測するモデルの事前訓練を行い、RLを使用して結果のエージェントを洗練させた(Scheller et al., 2020)。

第4位のチームであるCraftRLは、グラウンデッドアクションをオプションに集約し(Sutton et al., 1999)、メタコントローラを使用してオプション間の選択を行った。彼らは、行動のクローニングを使用してデモデータ上でメタコントローラを事前に訓練した。第5位のチームであるUEFDRLは、MineRLデータセットから人間の行動を模倣するように訓練された単一の深層残差ニューラルネットワークを使用した(Kanervisto et al., 2020)。このチームは、環境の複雑さに対処するために行動離散化を使用した。第6位のチーム、TD240は、報酬関数として敵対的逆RLに基づくdiscriminator soft actor criticを使用した。

7位のLAIRチームは、階層型RLアルゴリズムであるメタ学習共有階層（MLSH）（Fransら、2018年）を使用し、環境の相互作用を用いてMLSHを訓練する前に、人間のデータを用いてマスターとサブポリシーを事前に訓練した。8位のチームであるElytraは、環境に少量の確率性を追加したり、カメラの動きを1自由度に制限するなどの修正を加えたRainbowベースラインを提出した。しかし、彼らは値関数のアンサンブルを学習するというアイデアを模索しており、このアプローチは有望であると考えている。9位のkarolisramは、PPOのベースラインを使用し、フレームスキップの削除やアクションスペースの縮小などの修正を行った。

4.3. Special Awards

学習アルゴリズムの性能評価に加えて、研究貢献度の高いチームに賞を授与した。本コンテストは初年度の開催ということもあり、純粋に模倣学習に基づくものと、人間の事前行動を使用しないRLに基づくものの2つの極端で対照的な研究パラダイムに賞を授与した。
前者の研究賞はmc_rlさんに、後者の研究賞はkarolisramさんに授与しました。これらの特別賞が、将来の参加者に、たとえそれが性能を犠牲にしてでも、解の空間を最大限に探索することを奨励するものであることを期待している。

5. Organizational Outcomes

我々は、競争の重要な組織的成果を記述する。我々はまず、第 5.1 節で我々が選択したルールセットの影響を提示することから始める。次に、第 5.2 節では、競技会資料の配布の有効性について議論する。最後に、第 5.3 節では、我々が選択した評価方法の効果をまとめる。

5.1. Repercussions of the Rules

他の多くの DRL 競技とは異なり、私たちはフィーチャーエンジニアリングとハードコード化されたポリシーによって、ドメイン知識の使用を制限しようとした。
このルールセットにより、より一般的な方法を使用するようになったが、参加者から多くの明確な質問を受けることにもなった。
これらの質問は様々なコミュニケーションチャネルで行われたため、重複した質問があり、単一の包括的な答えはなかった。
将来的には、ルールを明確にし、ドメイン知識の使用をより強固に制限する場を設けたいと考えてる。

ドメイン知識の利用制限の副次的な効果として、このルール違反によるラウンド1の提出物のチェックが困難になったことが挙げられる。
訓練時間とサンプル数の制限は定量的な制限であるため、施行が容易である。競技者の提出物が「ホールドアウト」環境で訓練されていなかったため、委員会は手動で指定されたポリシーやその他の違反を特定するために、予想以上の作業時間を手動でコードをレビューしていた。

5.2. Effectiveness of Competition Materials

3.3 節で述べたように、我々は参加者に Gym 環境、データセット、ベースライン手法の実装としてのタスクを提供した。
環境とデータセットは競技会が始まる前に完成していたが、ベースラインは共同研究者である Preferred Networks への環境提供が遅れたため、競技会が発表された後に開発された。
しかし、Preferred Networksは迅速にベースラインを提供し、参加者がラウンド1でベースラインを使用できるようにしてくれたため、多くの参加者がこのベースラインが独自のアルゴリズムを開発する上で重要であることに気付いた。
今後コンペティションでは、ベースラインが完成した今、コンペティションが開始され次第、ベースラインを提供できるようにする予定である。

データは容易に入手可能であり、参加者は概ねうまく利用することができた。提供されたジム環境は、Malmo Minecraft環境のラッパーである(Johnson et al., 2016)。
Malmoを標準化された方法でラッピングすることに加えて、バグを修正し、より速く、より効率的なトレーニングを可能にする機能を追加した。これらの修正により、Minecraftでの作業への関心が高まり、いくつかの学術団体から環境のさらなる拡張について連絡を受けた。

参加者の提出物は、3.2項で概説されているように、特定のDockerフォーマットに従わなければならない。標準コンテナを使用することで、両ラウンドの評価プロセスが合理化され、時間の節約にもなった。私たちは、提供されたコンテナの使用方法についての情報を提供したが、参加者からのフィードバックに基づいて、提供された構造を使用してエージェントを提出する方法についてのステップバイステップのデモンストレーションを含むように、この文書を拡張する予定である。

5.3. Impact of Evaluation Methodology

計算予算を明示する必要性と、参加者を制限したくないことのバランスを考慮して、2 回のラウンドを選択した。
第1ラウンドでは参加できるチーム数を制限しなかったが、第2ラウンドに移行するチーム数をあらかじめ指定した。
その結果、第2ラウンドではすべての応募作品の再トレーニングを行うことを約束することができた。これは、トレーニング時間の制限が厳しいことと、トレーニングと評価をすべて行う特定のシステムを選択したために可能となった。この構造のおかげで、評価のために予想以上に多くの計算資源を使用することはなかった。

ただし、トレーニング時間に対するこれらの同じ厳しい制限により、最終結果の取得が遅れた。
競合他社の提出期限を遅らせたため、提出から結果が発表されるまでの時間が短縮された。
特定のシステムでトレーニングを一定の日数行う必要があったため、個々の参加者の提出物の実行を並列化したり、より高速なハードウェアで実行したりすることはでなかった。 遅延にもかかわらず、再現性とサンプル効率の利点により、今後のコンテストでは同様の制限を使用する。

セクション3.3で述べたように、第2ラウンドの各チームには、手法のトレーニングと検証を可能にするために、1500ドルのAzureクレジットの計算助成金を提供した。トレーニング時間の制限のため、参加者は、最終的なアプローチのトレーニング時間を延長するために残りの計算時間を費やすことにインセンティブを与えられなかった。競技終了後も手法の開発を続けられるだけの計算時間が残っているチームもあったため、各チームに十分な金額を配分したと考えている。

最後に、我々は新しい視覚的領域ランダム化手法(a novel visual domain randomization method)を効果的に利用して一般化とルール遵守を確保したが、参加者は帰納的バイアスを利用して行動空間を形成することに多大な労力を費やしていた。将来コンペティションで完全に一般化可能な競争結果を得るために、我々は環境の行動空間の意味的なラベルを削除し、評価中に行動空間にランダムな双射影マッピング(bijective-mapping)を適用することを計画している。

6. Conclusion

私たちは、以下のようなアルゴリズムの開発を促進するために、NeurIPS2019で「Sample Efficient Reinforcement Learning on Sample Efficient Reinforcement Learning Using Human Priors」というコンペティションを開催した。
1) 強化学習と並行して人間のデモンストレーションを使用し、
2) サンプル効率が高く、
3) 一般的なAIコミュニティが利用しやすいアルゴリズムの開発を促進
することを目的としている。

応募作品をまとめ、異なるラウンドでの競争相手のパフォーマンスを見てみた。
また、競技規則の効果、提供された競技資料、評価方法についても議論した。
本大会の結果が概ね良好であったことから、再度の開催を予定している。
ダイヤモンドを獲得したチームがなかったため、同じタスクである ObtainDiamond に集中する予定である。
また、一般化可能でロバストな学習方法の開発を促進するパラダイムも維持する予定である。
再開催の際には、ルールを明確にし、参加方法のデモンストレーションを増やし、参加者の増加を目指す。

Acknowledgments
We thank Microsoft Azure for providing the computational resources for the competition, NVIDIA for providing prizes, AIJ for funding the inclusion grants, and Microsoft Research for funding travel grants. We also thank AIcrowd for hosting and helping run the competi- tion, and Preferred Networks for providing the baseline method implementations. Finally, we thank everyone who provided advice or helped organize the competition.

補足

ObtainDiamondタスクと書かれているが2020年のコンペティションではMineRLObtainDiamondVectorObf-v0

動画

1位(Round 2?) https://www.youtube.com/watch?v=7J2HMUimj1A

本人による解説動画（ロシア語）： https://www.youtube.com/watch?v=7J2HMUimj1A
Round 1: https://www.youtube.com/watch?v=7J2HMUimj1A&feature=youtu.be&t=2015
Round 2: https://www.youtube.com/watch?v=7J2HMUimj1A&feature=youtu.be&t=2100

サブタスクについて

以下にRewardが書かれている。
https://minerl.io/docs/environments/index.html#minerlobtaindiamondvectorobf-v0

<Item reward="1" type="log" />
<Item reward="2" type="planks" />
<Item reward="4" type="stick" />
<Item reward="4" type="crafting_table" />
<Item reward="8" type="wooden_pickaxe" />
<Item reward="16" type="cobblestone" />
<Item reward="32" type="furnace" />
<Item reward="32" type="stone_pickaxe" />
<Item reward="64" type="iron_ore" />
<Item reward="128" type="iron_ingot" />
<Item reward="256" type="iron_pickaxe" />
<Item reward="1024" type="diamond" />

https://minerl.io/competition/ の中盤辺り、"The stages of obtaining a diamond."にも説明がある。

2020年のコンペティション

リーダーボード。Baseline PFRL SQILが強すぎる笑