AlphaStarの論文を読むその９（マルチエージェント学習）

マルチエージェント学習

リーグトレーニングはマルチエージェント強化学習アルゴリズムであり、セルフプレイトレーニング中によく発生するサイクルに対処し、多様な戦略を統合するために設計されている。
訓練中に、エージェント（RLアルゴリズムによって訓練されている）からのパラメータを新しいプレイヤー（固定された固定パラメーターを持つ）として定期的に保存することにより、リーグにデータを取り込む。
また、リーグ内のすべてのプレイヤーに対するパフォーマンスに関する最新情報をエージェントに提供するために、内部利得(payoff)の推定値を継続的に再評価する（拡張データ図6のEvaluatorsを参照）。

拡張データ図6|トレーニングインフラストラクチャ|リーグ全体のトレーニング設定

f:id:TadaoYamaoka:20191125083339p:plain

優先順位付きFictitious Self-Play

セルフプレイ（SP）アルゴリズムは、3つのすべての種族で最新のエージェント間でゲームをプレイする。
このアプローチは、戦略空間でサイクルを追跡する可能性があり、単独ではうまく機能しない（図3D）。

f:id:TadaoYamaoka:20191125084818p:plain

Fictitious Self-Play（FSP）は、リーグ内の以前のすべてのプレイヤーと対戦することでサイクルを回避する。
ただし、多くのゲームは、ほぼ100％のゲームで敗北したプレイヤーに対して無駄になる。
そのため、優先順位付きFictitious Self-Play（PFSP）を導入する。
リーグで均一に対戦相手をサンプリングする代わりに、マッチメイキングメカニズムを使用して、良い学習の信号を提供する。
学習エージェント𝐴が与えられた場合、以下の確率で候補セット𝒞から凍結した相手𝐵をサンプリングする。

$\displaystyle \frac{f(\mathbb{P}[A \text { beats } B])}{\sum_{C \in \mathcal{C}} f(\mathbb{P}[A \text { beats } C])}$

ここで、𝑓: [0,1] → [0, ∞)は重み関数である。

対戦相手の強さの制御

$f_{\text {hard }}(x)=(1-x)^{p}$ で選択すると、PFSPは最も難しいプレイヤーに焦点を合わせる。ここで、 $p \in \mathbb{R}_{+}$ は、結果の分布のエントロピーを制御する。
$f_{\text {hard }}(1)=0$ であるため、エージェントが既に負かした対戦相手とのゲームは行われない。
最も難しいプレイヤーに焦点を当てることにより、エージェントは平均パフォーマンスを最大化するのではなく、リーグの全員を倒す必要がある。これは、平均勝率の追求が悪用されやすい方策につながる可能性があるStarCraftのような非常に非推移的なゲームではより重要です。
このスキームは、PFSPのデフォルトの重み付けとして使用される。
その結果、理論的には、FSPが課すmax-avgとは対照的に、 $f_{\text {hard }}$ はmax-min最適化の滑らかな近似の形式として見ることができる。
特に、これはエクスプロイトからの情報を統合するのに役立つ。それらは強力ではあるが頻度の少ないカウンター戦略であり、均一な混合ではそれらを無視することができるためである（拡張データ図5）。

拡張データ図5 | 図3 CおよびDのマルチエージェントアブレーションのより詳細な分析

f:id:TadaoYamaoka:20191127084422p:plain

PFSPベースの訓練は、考慮されたすべての測定値でFSPよりも優れている。相対的な人口パフォーマンスで測定される人口がより強く、悪用されにくいソリューションを提供し、対応するリーグに対してより良い最終エージェントパフォーマンスを持つ。

対戦相手選択の代替ソリューション

最も難しい相手と対戦するだけでは、はるかに強い相手とのゲームを無駄にする可能性があるため、PFSPは代替のカリキュラム、 $f_{\text {var }}(x)=x(1-x)$ も使用する。
このカリキュラムは、メインエクスプロイトと低迷しているメインエージェントに使用する。

感想

サイクル（じゃんけんのような関係）を追跡する問題に対処するため、AlphaStarではFictitious Self-Playというアルゴリズムでマルチエージェント学習が行われています。
Fictitious Self-Playは、以前のプレイヤーと対戦することでサイクルを回避できますが、無駄な対戦が多くなるとという問題があるようです。
そこで、対戦相手の選択に優先順位を付けて、勝率が低い相手を優先的に選択し、すでに100%勝つ相手とは対戦しないように制御しています。
平均勝率を最大化を目標にすると、特定の相手に対してだけ有効な戦略で勝率を稼ぐといった戦略を覚えてしまい弱点が残ったままになるため、最も苦手な相手に焦点を当てててリーグ全体に勝つことを目標にしています。
ただし、リーグ内で低迷しているエージェントは、最も強い相手とばかり対戦して負けてばかりでは成長しなくなるため、そのようなエージェントとメインエクスプロイトエージェントには中間の相手を選択する方法も取られています。

(続く)