MuZeroの論文を読む（概要、導入、先行研究）

MuZeroの論文を読んでいきます。
基本的にだらだら訳していくだけです。
途中で感想を書いていきます。

概要

プランニング能力を備えたエージェントを構築することは、人工知能の追求における主な課題の1つである。
ツリーベースのプランニング方法は、完全なシミュレーターが利用できるチェスや囲碁などの挑戦的なドメインで大成功を収めている。
ただし、実際の問題では、環境を支配するダイナミクスはしばしば複雑で未知である。
この研究では、ツリーベースの探索と学習モデルを組み合わせることにより、基礎となるダイナミクスの知識がなくても、挑戦的で視覚的に複雑な領域で超人的なパフォーマンスを実現するMuZeroアルゴリズムを紹介する。
MuZeroは、反復的に適用されたときに、プランニングに最も直接関係する量（報酬、行動選択方策、および価値関数）を予測するモデルを学習する。
モデルベースのプランニングアプローチが過去に苦労してきた57種類のAtariゲーム(AI技術をテストするための標準的なビデオゲーム環境)で評価したとき、新しいアルゴリズムは最先端を達成した。
ゲームルールの知識がなくても、囲碁、チェス、将棋で評価した場合、MuZeroは、ゲームルールが提供されたAlphaZeroアルゴリズムの超人的なパフォーマンスと一致した。

導入

先読み探索に基づくプランニングアルゴリズムは、人工知能で顕著な成功を収めている。
人間の世界チャンピオンは、チェッカー、チェス、囲碁、ポーカーなどの古典的なゲームで敗北しており、プランニングアルゴリズムは、物流から化学合成までのアプリケーションで現実世界に影響を与えた。
ただし、これらのプランニングアルゴリズムはすべて、ゲームのルールや正確なシミュレーターなどの環境のダイナミクスに関する知識に依存しており、ロボット、産業用制御、インテリジェントアシスタントなどの実世界のドメインへ直接適用する妨げになっている。

モデルベースとモデルフリー

モデルベースの強化学習（RL）は、まず環境のダイナミクスのモデルを学習し、次に学習したモデルに関してプランニングすることにより、この問題に対処することを目的としている。
通常、これらのモデルは、真の環境状態の再構築、または一連の完全な観測に焦点を合わせている。
ただし、Atari 2600ゲームなどの視覚的な領域では、従来の研究は最先端からはほど遠いままである。
代わりに、最も成功した方法はモデルフリーRLに基づいている。
つまり、環境との相互作用から最適な方策や価値関数を直接推定する。
ただし、モデルフリーアルゴリズムは、チェスや囲碁などの正確で洗練された先読みを必要とする分野では、最先端とはかけ離れている。

MuZero

この論文では、視覚的に複雑なドメインセットであるAtari 2600で最先端のパフォーマンスを達成しながら、チェス、将棋、囲碁などの精密なプランニングタスクで超人的なパフォーマンスを維持する、モデルベースRLへの新しいアプローチであるMuZeroを紹介する。
MuZeroは、AlphaZeroの強力な探索および探索ベースの方策反復アルゴリズムに基づいているが、学習モデルを訓練手順に組み込む。
MuZeroは、AlphaZeroを、シングルエージェントドメインや中間タイムステップで報酬がないドメインなど、より広範な環境に拡張する。

アルゴリズムの概要

アルゴリズムの主なアイデア（図1に要約）は、プランニングに直接関連する将来の側面を予測することである。
モデルは入力として観測（例：囲碁の盤面やAtariの画面）を受け取り、それを隠れ状態に変換する。
隠れ状態は、前の隠れ状態と仮想の次の行動を受け取る再帰プロセスによって繰り返し更新される。
これらのすべてのステップで、モデルは方策（プレイする手など）、価値関数（予測される勝者など）、および即時報酬（手をプレイすることで獲得したポイントなど）を予測する。
モデルは、これら3つの重要な量を正確に推定することを唯一の目標として、エンドツーエンドで訓練され、探索によって生成される方策と価値の推定値と観測される報酬を一致させるようにする。
元の観測を再構築するために必要なすべての情報を取得するための隠れ状態に対する直接的な制約や要件はなく、モデルが維持および予測しなければならない情報量を大幅に削減する。
また、隠れ状態が環境の未知の真の状態に一致する要件もない。また、状態のセマンティクスに対するその他の制約もない。
代わりに、隠れ状態は、現在および将来の価値と方策の予測に関連するあらゆる方法で状態を表すことができる。
直感的には、エージェントは、最も正確なプランニングにつながるルールまたはダイナミクスを内部で生み出すことができる。

f:id:TadaoYamaoka:20191121214604p:plain

先行研究

強化学習は、モデルベースとモデルフリーの2つの主要なカテゴリに分類できる。
モデルベースのRLは、中間ステップとして、環境のモデルを構築する。
古典的に、このモデルは、次の状態を予測する状態遷移モデルと、その遷移中に予想される報酬を予測する報酬モデルという2つのコンポーネントで構成されるマルコフ決定プロセス（MDP）で表される。
モデルは通常、選択された行動、またはオプションなどの時間的に抽象的な動作を条件とする。
モデルが構築されると、価値反復やモンテカルロ木検索（MCTS）などのMDPプランニングアルゴリズムを適用して、MDPの最適な価値または最適な方策を計算するのは簡単である。
大規模または部分的に観測された環境では、アルゴリズムは最初にモデルが予測する状態表現を構築する必要がある。
表現学習、モデル学習、およびプランニングのこの3者間の分離は、エージェントが効果的なプランニングのための表現またはモデルを最適化できないため、潜在的に問題があり、その結果、たとえばプランニング中にモデリング誤差が悪化する可能性がある。

モデルベースRL

モデルベースRLのための一般的なアプローチは、ピクセルレベルで観測ストリームを直接モデリングすることに焦点を当てている。
深い確率的なモデルは、複合誤差の問題を緩和する可能性があるという仮説が立てられている。
ただし、ピクセルレベルの粒度でのプランニングは、大規模な問題では計算上扱いにくい。
他の方法では、ピクセルレベルで観測ストリームを再構築する*1 *2、または将来の潜在状態を予測するのに十分な潜在状態空間モデルを構築する*3 *4。
これにより、より効率的なプランニングが容易になるが、モデル容量の大部分は無関係な可能性のある詳細に集中する。
これらの従来の方法はいずれも、Atariなどの視覚的に複雑なドメインで効果的なプランニングを容易にするモデルを構築していない。結果は、データ効率の面でも、適切に調整されたモデルフリーの方法の方が優れている*5。

モデルベースのRLの新しいアプローチ

モデルベースのRLへのまったく異なるアプローチが最近開発され、価値関数の予測にエンドツーエンドで焦点を当てている*6。
これらの方法の主なアイデアは、抽象MDPでのプランニングが実際の環境でのプランニングと同等になるように、抽象MDPモデルを構築することである。
この等価性は、価値の等価性を確保することで実現される。つまり、同じ実際の状態から開始して、抽象MDPを介した軌跡の累積報酬が実際の環境での軌跡の累積報酬と一致するということである。

predictron

predictron*7は、（行動なしで）価値を予測するための価値等価モデルを最初に導入した。
基礎となるモデルはまだMDPの形式をとっているが、その遷移モデルが環境内の実際の状態に一致する必要はない。
代わりに、MDPモデルはディープニューラルネットワークの隠れ層と見なされる。
拡張されたMDPは、報酬の予想累積合計が実際の環境に関する予想値と一致するように（たとえば、TD学習によって）訓練される。

価値等価モデルの拡張

価値等価モデルは、その後、（行動付き）価値の最適化に拡張された。
TreeQN*8は、抽象MDPモデルを学習し、そのモデル（ツリー構造のニューラルネットワークで表される）での木探索が最適価値関数に近似するようにする。
価値反復ネットワークはローカルMDPモデルを学習し、そのモデル（畳み込みニューラルネットワークで表される）での価値反復が最適価値関数を近似するようにする。
価値予測ネットワーク*9は、おそらくMuZeroに最も近い先行研究であり、実際の行動に基づいたMDPモデルを学習する。
つまり、拡張されたMDPは、単純な先読み探索によって生成された実際の行動シーケンスを条件とする報酬の累積合計が実際の環境と一致するように訓練される。
MuZeroとは異なり、方策の予測はなく、探索では価値の予測のみが使用される。

感想

AphaZeroでは、強化学習で行動を選択する際に、MCTSで環境（遷移確率）をモデル化していました。これはモデルベースと呼ばれる手法です。
Atariゲームのような視覚的に複雑な領域や、現実世界のような複雑なドメインでは、環境がモデリングできないためモデルフリーの手法が用いられています。
AlphaStarでも、行動空間が広すぎるため先読みができないため、モデルフリーの手法がとられていました。
しかし、囲碁や将棋のように正確な先読みが必要な領域ではモデルフリーの手法では、パフォーマンスがでないことが述べられています。

Atariのような視覚的に複雑な領域でもモデルベースのアプローチを適用できるようにしたというのが、この論文の主旨のようです。
アルゴリズムの詳細は、この後読んでいきます。
(続く)