論文で理解するMuZeroの概要｜論文で理解する深層強化学習の研究トレンド #4

連載の詳細の経緯は#1に記しましたが、深層強化学習の研究トレンドを論文を元に把握していくシリーズとしています。

#1ではApe-X[2018]について、#2ではR2D2[2019]について、#3ではR2D3についてご紹介しました。

論文で理解するApe-Xの概要｜論文で理解する深層強化学習の研究トレンド #1 - lib-arts’s diary

論文で理解するR2D2の概要｜論文で理解する深層強化学習の研究トレンド #2 - lib-arts’s diary

論文で理解するR2D3の概要｜論文で理解する深層強化学習の研究トレンド #3 - lib-arts’s diary

#4ではAlphaGoなどで用いられているmodel-basedなアプローチを用いてAtariのベンチマークでも結果を出したモデルである"MuZero(Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model)"についてご紹介します。

[1911.08265] Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model

以下、目次になります。
1. MuZeroの概要（Abstract、Introductionの確認）
1-1 Abstractの確認
1-2 Introductionの確認(Section1)
2. 論文の重要なポイントの抜粋
2-1. Prior Work(Section2)
2-2. MuZero Algorithm(Section3)
2-3. Results(Section4)
2-4. Conclusions(Section5)
3. まとめ

1. MuZeroの概要（Abstract、Introductionの確認）
1-1 Abstractの確認
1-1節ではAbstractの内容を確認しながら概要について把握します。以下各文の和訳とともに解説を行います。

Constructing agents with planning capabilities has long been one of the main challenges in the pursuit of artificial intelligence. Tree-based planning methods have enjoyed huge success in challenging domains, such as chess and Go, where a perfect simulator is available.

和訳：『プランニングによってエージェントを構築する手法は人工知能の分野の探求において長らく主要な課題であった。木構造がベースの(tree-based)プランニングの手法は、チェスや囲碁のような完全なシミュレーションが可能なドメインにおいて大きな成功をおさめてきた。』
モンテカルロ木探索(MCTS; Monte Carlo Tree Search)の記事でもまとめましたが、チェスや囲碁などではこのような探索ベースの手法が成功をおさめてきました。代表的な例としては、AlphaZeroなどが挙げられます。

However, in real-world problems the dynamics governing the environment are often complex and unknown.

和訳：『しかしながら、変動(dynamics)が支配する実世界の環境における問題はしばしば複雑で、環境も事前に知ることができない。』
チェスや囲碁のような環境がモデリングできる状況とは異なり、実世界における問題は複雑で環境モデルを事前に設定することができないとここでは言及されています。そのため、Atariのゲームに取り組んだDeep Q-Network、Rainbow、R2D2などの研究や、より難しいタスクに取り組んだR2D3のような研究ではmodel-basedではなく、model-freeのアプローチが取られています。

In this work we present the MuZero algorithm which, by combining a tree-based search with a learned model, achieves superhuman performance in a range of challenging and visually complex domains, without any knowledge of their underlying dynamics.

和訳：『この研究では我々はMuZeroのアルゴリズムを提案する。MuZeroのアルゴリズムは学習されたモデル(learned model)に木探索(tree-based search)を組み合わせることで、元々の環境モデルに関する知識なして視覚的に複雑な問題において人間を上回るパフォーマンスを実現した。』
この辺はSutton本のCh.8のdiagramなどにおいて、経験から環境モデルを学習し、シミュレーションによって行動方策を決めていくことが対応していると考えられそうです。詳細についてはMuZeroのContributionにあたる内容だと思われるので、詳細を確認するにあたってはこの辺を意識して把握するのが良いと思われます。

MuZero learns a model that, when applied iteratively, predicts the quantities most directly relevant to planning: the reward, the action-selection policy, and the value function. When evaluated on 57 different Atari games - the canonical video game environment for testing AI techniques, in which model-based planning approaches have historically struggled - our new algorithm achieved a new state of the art.

和訳：『MuZeroは繰り返しで適用されることでプランニングに最も直接関係する指標を予測する環境モデルを学習する。指標としては、報酬、行動選択の方策(action-selection policy)、そして価値関数(value function)である。57の異なるAtariゲーム(AI技術をテストするにあたっての標準的なビデオゲームの環境で、model-basedのプランニングのアプローチは長らく苦戦してきた)で評価したところ、我々のアルゴリズムは新たなSotAを実現した。』
Atariのような複雑な環境を前提とした際に、model-basedのアプローチはチェスや囲碁ほどはうまくはいかず、長い間苦戦してきたとされています。それに対し、MuZeroではmodel-basedのアプローチに基づいてSotAを達成するというのが強調ポイントになっています。

When evaluated on Go, chess and shogi, without any knowledge of the game rules, MuZero matched the superhuman performance of the AlphaZero algorithm that was supplied with the game rules.

和訳：『囲碁やチェス、将棋においてもゲームのルールの知識なしでMuZeroは人間を超えるパフォーマンスを示したAlphaZeroと同等のパフォーマンスを示した。』
ゲームのルールが与えられていたAlphaZeroに対して、MuZeroはゲームのルールなしで同等の性能を示したとされています。しかもAtariにおけるベンチマークも更新したとされているので、汎用的な成功をおさめていることがここから読み取れます。

1-2 Introductionの確認(Section1)
1-2ではIntroductionの確認を行っていきます。以下、パラグラフ単位で確認していきます。

第一パラグラフでは、model-basedなアプローチに基づいたプランニングアルゴリズムはchessやGoやpokerなどの分野で大きな成功を挙げたとされています。その一方で、ゲームのルールや正確なシミュレーターを必要とすることからロボティクスなどの実世界的なドメインへの応用については取り組みがうまくいっていなかったとされています。

第二パラグラフでは、model-basedのアプローチではmodelの学習という観点からこの問題に取り組もうとしたけれども、Atari2600のようなベンチマークではmodel-freeのアルゴリズムの結果を上回れなかったとされています。一方で、model-freeのアルゴリズムではchessやGoのような精巧で洗練されたドメインではSotAから程遠い状況にあることについても言及されています。

第三パラグラフでは、第二パラグラフまでの話を受けて、Atari2600でもSotAを達成したmodel-basedなアプローチとしてMuZeroを紹介しています。MuZeroはAlphaZeroのパワフルな検索や検索ベースの方策イテレーションのアルゴリズムをベースに成り立っているとされています。

第四パラグラフではFigure1を主に参照しているのでこちらを確認します。Aはプランニングにあたっての探索、BはAで探索した結果に基づいたActionの選択、Cは環境モデルの学習を表すとされています。AとBについてはAlphaZeroと同様なtree-basedな探索を用いている一方で、Cの環境モデルの学習がMuZeroにおける主要なContributionと捉えて良さそうです。

2. 論文の重要なポイントの抜粋
2-1. Prior Work(Section2)
MDPやMonte-Carlo tree search(MCTS)について言及されています。model-basedなアプローチについて主に言及されているようですが、Sutton本のCh.8の内容で事前知識的に十分だと思われるのでここでは省略します。

2-2. MuZero Algorithm(Section3)
まず問題設定について見ていきます。

上記では、環境モデルが推論する三つの指標(quantities)について言及されています。三つの指標としては、方策(policy)、価値関数(value function)、報酬(reward)がそれぞれ挙げられています。
次に探索(プランニング)についての言及を確認します。

環境モデルが与えられた状況では上記で例示されているように、価値関数を大きくするような選択を取り続けるなどの方法で探索(プランニング)を行うことができるとされています。

また、環境モデルの学習にあたっては(1)の式を誤差関数に用いて最適化を行うとされています。

2-3. Results(Section4)
Resultsでは実際に行った実験の結果がまとめられています。

まず、AlphaZeroとの比較ですが、上記のように概ね同等のパフォーマンスを実現できていることが確認できます。Chess、Shogi、GoのそれぞれにおいてオレンジのラインがAlphaZeroで、青のラインがMuZero(横軸は学習ステップ)であるとされています。また、Atariにおいては人間のパフォーマンスとの比較が行われています。オレンジの実線が人間のスコアの平均、点線が人間のスコアの中央値であるとされています。

次にAtariのベンチマークにおける、Ape-XやR2D2などのmodel-freeのアルゴリズムとの比較についてまとめられています。R2D2[2019]を上回り、SotAの結果を出していることが読み取れます。

2-4. Conclusions(Section5)
ここまでまとめてきた内容とかぶるため省略します。

3. まとめ
#4ではmodel-basedのアプローチとしてAtariのベンチマーク更新を実現した研究であるMuZero(Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model)について取り扱いました。R2D2の精度を上回っており、model-freeのアプローチとmodel-basedのアプローチを見直すきっかけになるエポックメイキングな結果になっていると思われます。
一方で、SotAの達成にあたってR2D2とそれほど大きな精度の差がまだついていないことと、R2D3のようにAtariよりもさらに複雑な環境下における振る舞いなど、まだまだ注目点が多いと思われるので、この辺については今後の研究トレンドにも注目が必要だと思われます。
#5ではMuZeroの論文のベースの研究となっているAlphaZero[2018]について取り扱います。