報酬のランダム化により、マルチエージェントゲームにおける多様な戦略的行動が発見され、研究者は新しいアルゴリズムを提案する

本論文では、研究者らは報酬空間を探索するための新しいアルゴリズム RPG (報酬ランダム化ポリシー勾配) を提案し、複数のナッシュ均衡 (NE) を持つ困難なマルチインテリジェンスタスクでそれを実験的に検証しました。実験結果によると、RPG は従来のポリシー/アクション空間探索アルゴリズムよりも大幅に優れたパフォーマンスを発揮し、多くの興味深く人間が理解できるエージェント行動戦略を発見します。さらに、この論文では、RR によって取得された多様な戦略プールを使用して、適応機能を備えた新しい戦略をトレーニングするという、RPG アルゴリズムの拡張を提案しています。

フランス啓蒙思想家ジャン＝ジャック・ルソーは著書『人間不平等の起源』の中で、鹿狩りについての物語を述べています。一群のハンターが罠の横で静かに鹿が現れるのを待っていました。鹿を狩ればハンター全員の食糧となるため、その利益は大きかったのですが、鹿は非常に警戒心が強いため、全員が辛抱強く待つ必要がありました。この時、ウサギが現れました。ウサギはサイズが小さかったので、一人で狩るのに成功しましたが、それに伴う利益も非常に小さかったです。

では、すべてのハンターには 2 つの選択肢があります。鹿が現れるのを待ち続けるか、飛び上がってすぐにウサギを捕まえるかです。ハンターがすぐにウサギを狩ることを選択した場合、ウサギを捕まえて利益は少なくなります。ハンターが鹿を待ち続けることを選択し、他のすべてのハンターも鹿を待ち続けることを選択すれば、最終的に鹿を狩って最大の利益を得ることができますが、他のハンターがすぐにウサギを狩ることを選択すると、鹿を待つことを選択したハンターは飢えるしかありません（ウサギを捕まえることも、再び鹿を狩る機会もありません）。

図 1: StagHunt ゲーム、a>b>=d>c

2 人のハンターのケースを検討し、さまざまな状況の利点を抽象化すると、ゲーム理論における非常に古典的な 2x2 マトリックス ゲーム StagHunt が導き出されます。図 1 に示すように、各ハンターは 2 つの行動を実行できます。鹿狩り (Stag、略称 S) とウサギ狩り (Hare、略称 H) です。2 人のハンターが両方とも鹿狩りを選択した場合 (S、S)、最大の利益 a (十分に食べる) が得られます。両方ともウサギ狩りを選択した場合 (H、H)、より小さな利益 d (ウサギを分け合う必要がある) が得られます。一方が鹿狩り、もう一方がウサギ狩りを選択した場合 (S、H)、ウサギ狩りをする人は利益 b (ウサギだけを食べる) が得られ、鹿狩りをする人は利益 c (飢える) が最小限になります。これらの報酬は、サイズ関係 a (ウサギの全身を食べる) > b (ウサギを 1 匹だけ食べる) >= d (ウサギを 2 人で分け合う) > c (飢える) を満たします。

図2: StagHuntゲームにおけるPPOのパフォーマンス。a=4、b=3、d=1、ランダムシード10個

このゲームには 2 つの純粋戦略ナッシュ均衡 (NE) があります。1 つはStag NEで、両方のハンターが鹿を待つことを選択し、各ハンターは高い報酬を得ることができますが、これはリスクの高い協力戦略です。なぜなら、ハンターの 1 人が協力しないことを選んだとしても、そのハンター自身の利益は、最大利益 a (十分に食べる) から利益 b (ウサギだけを食べる) へと大幅に変わることはないからです。しかし、もう 1 人のハンターの損失は大きく、最大利益 a (十分に食べる) から最小利益 c (飢える) へと変わります。損失（つまり AC）が大きいほど、ハンターが協力を選択するリスクが高くなります。もう 1 つのナッシュ均衡はHare NEです。つまり、両方のハンターがウサギを狩ることを選択します。各ハンターはより低い収益しか得られませんが、これは保守的な戦略です。なぜなら、相手が何を選択しても、一定の利益が得られるからです。つまり、相手が鹿を狩ることを選択した場合は、より大きな利益 b (ウサギを単独で食べる) が得られ、ウサギを狩ることを選択した場合は、より小さな利益 d (ウサギを共有する) が得られます。このタスクでは、既存の強化学習アルゴリズムはどの NE に収束するでしょうか?著者は、a=4、b=3、d=1 を固定し、c の値を変えて実験を行いました。図 2 から、鹿のみを狩るペナルティが大きいほど、既存のアルゴリズムが Stag NE に収束する確率が低くなり、保守的なウサギ狩り戦略を選択する傾向が高くなることがわかります。これは前回の分析と一致しています。

では、強化学習を最高のリターンをもたらす戦略に収束させるにはどうすればよいでしょうか?この問題を解決するために、清華大学、北京大学、カリフォルニア大学バークレー校などの研究者は、報酬ランダム化（RR）というシンプルで効果的な技術を提案しました。従来の強化学習における状態空間での探索方法とは異なり、報酬ランダム化は報酬空間での探索方法です。この研究は、ICLR 2021 会議のポスター論文として採択されました。

論文の宛先:
https://arxiv.org/abs/2103.04564

図 3 に示すように、極端な報酬設定のゲームでは、強化学習では通常、最適な戦略を探索することが困難です (左の図、灰色の領域は、最適なソリューションに収束する可能性のあるサブスペースを表しますが、極端な報酬のために非常に狭くなります)。ただし、他の報酬設定のゲームでは、同じ戦略を簡単に探索できます (右の図)。これが、論文の核となるアイデアにつながります。つまり、元のゲーム (StagHunt) の報酬をランダム化することで報酬が乱れ、問題は乱れたゲームで協力戦略を見つけることに変換され、その後元のゲームに戻って微調整を行い、最適な戦略を見つけます。

図3: 報酬のランダム化の模式図

さらに、この論文では、報酬のランダム化とポリシー勾配法 (PG) を組み合わせ、報酬空間を探索するための新しいアルゴリズム RPG (報酬ランダム化ポリシー勾配) を提案しています。実験結果によると、RPG は従来のポリシー/アクション空間探索アルゴリズムよりも大幅に優れたパフォーマンスを発揮することが示されており、著者らは RPG を使用して、多くの興味深く人間が理解できるエージェント行動戦略を発見しています。

まず、論文では GridWorld で実験を行いました。この実験では、Monster-Hunt というタスクがあります (図 4 を参照)。タスク設定は次のとおりです。図では、黄色と青を使用して 2 つのエージェントを表し、5*5 のグリッド内を移動できます。赤はモンスターを表し、グリッド内をランダムにさまようことができます。モンスターの特徴の 1 つは、最も近いエージェントに向かって移動することです。緑は食べ物のリンゴ（Apple）を表し、リンゴは動かすことができません。両方のエージェントが同時にモンスターに遭遇した場合、各エージェントは +5 の報酬を受け取ります。エージェントが単独でモンスターに遭遇した場合、-2 のペナルティが課せられます。エージェントはリンゴを食べることもでき、リンゴ 1 個につき +2 の報酬が与えられます。明らかに、このタスクには 2 つのナッシュ均衡があります。つまり、2 人のエージェントが同時にモンスターに遭遇する (高リスク、高報酬)、またはそれぞれがリンゴを食べに行く (低リスク、低報酬) です。

図4: モンスターハントのミッション図

図5: モンスターハントタスクにおけるさまざまなアルゴリズムのパフォーマンス比較

図 5 は、RPG を、標準のポリシー勾配法、エージェント間で報酬を共有するポリシー勾配法、集団ベースのアルゴリズム、および MAVEN、カウントベース、Diayn などのいくつかの探索アルゴリズムを含むさまざまなアルゴリズムと比較した結果を示しています。このタスクでは、RPG がベースラインを大幅に上回っていることがわかります。また、図からわかるように、RR ステージで最適な戦略が見つからなくても、RPG は微調整ステージを通じてパフォーマンスをさらに向上させ、最適な戦略を見つけることができることがわかります。それで、RPG はどのような戦略を発見したのでしょうか?リンゴを食べたりモンスターに遭遇したりという自然なプロセスのほかに、著者は他の 2 つの協力戦略も発見しました。図 6 (a) は、発見された次善の協力戦略を示しています。ゲーム開始後、2 人のエージェントは 5*5 グリッドの同じコーナーに移動し、その後合流してその場に留まります。モンスターの特性の 1 つは、最も近いエージェントに向かって移動することであるため、2 人のエージェントはその場に留まっていても一緒にモンスターに遭遇し、より高い報酬を得ることができます。この協力戦略は非常に合理的に思えます。では、より優れた協力戦略はあるのでしょうか。答えはイエスです。図6（b）はRPGが発見した最適戦略を示しています。ゲーム開始後、2つのエージェントは最初に収束し、次に一緒にモンスターに向かって移動します。さらに、モンスターもエージェントに向かって移動するため、一緒にモンスターに遭遇する速度が大幅に向上し、より高い利益が得られます。図 7 は最適な協力戦略のデモンストレーションアニメーションです。

図6: モンスターハント課題における2つの異なる協力戦略

図7 モンスターハントタスクにおける最適な協力戦略のデモンストレーション

次に、本論文で初めてオープンソース化され、本論文の大きな貢献でもある新しい環境 Agar.io を紹介します。 Agar.io は非常に人気のあるオンライン マルチプレイヤー ゲームです (ゲーム アドレス: http://agar.io)。各プレイヤーはマウスを使用して移動方向を制御し、自分よりも小さいエージェント (食べ物または他のプレイヤー) を食べることができます。この論文では、プレイヤーが 2 人の場合のみを検討しています。下の図 (a) はタスクの概略図を示しており、2 人のエージェントも黄色と青で表されています。赤はマップ上にランダムに生成された食べ物を表します。プレイヤーは自分より小さい食べ物や他のプレイヤーを食べることで報酬を得ます (報酬の大きさは食べた質量に等しい)。同様に、質量が失われるとかなりのペナルティが課せられます。次の図 (b) は、Split を使用して移動速度を上げて捕食を完了するなどの一般的なプレイヤーの行動を示しています。また、分割された部分は結合 (Merge) することもできます。知能体の質量が増加すると、その移動速度はどんどん遅くなり、狩りはますます難しくなり、より高い収益を得るためにプレイヤーは協力する必要があります。しかし、2 人のプレイヤーが互いに近い場合、質量が大きいプレイヤーは質量が小さいプレイヤーを攻撃することを選択する可能性が高く、それによって即時の報酬が得られ、協力関係が崩壊することになります。したがって、質量の少ないプレイヤーにとって、この協力戦略は非常に危険です。

図7 Agar.ioタスク図

あなたがプレイヤーだったら、どのような戦略を選びますか?その疑問を念頭に置いて、RPG で発見された、人間が理解できる興味深いプレイヤー戦略を 7 つ紹介します。

（１）協力戦略（図８）：２人のプレイヤーが協力して食料を特定のエリアまで運び、その後別々に狩りをする。

図8 (a) Agar.ioタスクにおける協力戦略

図8 (b) 共同デモンストレーション

（２）攻撃的戦略（図９）：２人のプレイヤーが互いに接近している場合、質量の大きいプレイヤーは質量の小さいプレイヤーを捕食することを選択する。

図9 (a) Agar.ioタスクにおける攻撃戦略

図9 (b) 攻撃のデモンストレーション

（３）非協力戦略（図１０）：２人のプレイヤーが個別に狩りをする。

図10: Agar.ioタスクにおける非協力的狩猟戦略

図11 Agar.ioタスクにおける積極的な協力戦略

（4）積極的協力戦略（図11）：2人のプレーヤーはほとんどの場合協力することを選択するが、時折攻撃的な行動をとる。

（５）犠牲戦略（図１２）：ゲーム開始後、２人のプレイヤーはそれぞれ単独で捕食を行う。一定時間後、質量の小さいプレイヤーはマップの境界で待機し、質量の大きいプレイヤーに自らを犠牲にする。質量の大きいプレイヤーはその後、すべての質量を制御して捕食を行う。

図12 (a) Agar.ioミッションにおける犠牲戦略

図12 (b) 犠牲のデモンストレーション

（６）永久戦略（図１３）：ゲーム開始後、２人のプレイヤーは別々に食料を狩ります。一定時間後、質量の大きいプレイヤーはマップの端で待機し、質量の小さいプレイヤーは質量の大きいプレイヤーに向かって食料を運び、狩りをします。その後、質量の大きいプレイヤーは質量の小さいプレイヤーの一部を非常に慎重に食べ、質量の小さいプレイヤーの残りの部分は外に出て食料を運び続けます。一定時間が経過すると、2 人のプレイヤーが役割を交換し、サイクルが何度も繰り返されます。これが永久機関という名前が付けられた理由です。

図13 (a) Agar.ioタスクにおける永続戦略

図13 (b) 永久機関のデモンストレーション

（７）バランス戦略（図１４）：RPGの微調整後に得られた最適戦略は、実は相互犠牲、個体捕食、協力のバランス戦略である。図１４からわかるように、RPGで学習した戦略の協力行動は若干低いものの、最も利益が高い。

図14 RPGはバランス戦略を学習しました（バランス）

論文の最後では、RPG アルゴリズムの拡張が示されています。新しい適応ポリシーは、戦略をランダム化することによって取得された多様な戦略プールを使用してトレーニングされます。戦略の適応性を検証するために、著者は Agar.io で興味深い実験を行いました。対戦相手の戦略はゲームの途中で切り替えられ、図 15 に示すように、Oracle 戦略と比較されます。たとえば、対戦相手の戦略が協力型から競争型に切り替わった場合、適応型戦略によって得られる報酬は競争型戦略の報酬よりもわずかに低くなりますが、協力型戦略の報酬よりも大幅に高くなります。また、対戦相手の戦略が競争型から協力型に切り替わった場合、適応型戦略によって得られる報酬は協力型戦略の報酬よりもわずかに低くなりますが、競争型戦略の報酬よりも大幅に高くなります。これは、トレーニングされたポリシーが実際に適応的であることを証明します。

図 15 Agar.io タスクにおける Adaptive 戦略と Oracle 戦略の結果の比較。戦略を切り替えた後の報酬のみがカウントされることに注意してください。

上記が論文の主な内容です。より詳細な実験と分析については、元の論文を参照してください。論文のソースコードと開発されたAgar.io環境はオープンソース化されています。コードガイドは次のとおりです。
https://github.com/staghuntrpg/RPG.