技術概要：不完全情報ゲームにおける自己対戦探索の加速のためのデータ拡張ゲーム開始

問題提起

大規模な不完全情報競争ゲーム（例：スタークラフト、ドータ、カウンターストライク）における近似均衡の発見は、大多数の実践者にとって計算的に実行不可能なままです。主なボトルネックは戦略的相互作用の解決そのものではなく、希薄な報酬、長い意思決定地平線、複雑な隠れ状態ダイナミクスを伴う環境に内在する「探索の難しさ」です。従来の自己対戦手法は、戦略的に重要なサブゲームに到達するために調整された行動の長いシーケンスを繰り返し探索することで計算リソースを浪費しがちですが、本質的に異なる高レベルの戦略的選択の集合は比較的小さいにもかかわらずです。

人間のデモンストレーションからの行動模倣（BC）は能力のブートストラップに一般的なアプローチですが、必要なスキルを学習するには広範な状態 - 行動軌跡を必要とします。さらに、不完全情報ゲームの既存のベンチマークは、実世界のドメインに見られる探索の課題（希薄な報酬、長い地平線）を欠くことが多く、探索を加速するように設計された手法の評価を困難にしています。

手法：データ拡張ゲーム開始（DAGS）

著者は、常にルート状態から再開するのではなく、オフラインのゲームプレイデータからサンプリングされた中間状態で強化学習（RL）のエピソードを初期化することにより、オンライン探索を加速する戦略である「データ拡張ゲーム開始（DAGS）」を提案します。

中核メカニズム

1. オフラインデータセット: この手法は、有能（必ずしも最適ではない）なゲームプレイから収集されたグローバル状態のオフラインデータセット $D$ を利用します。これらの状態は、戦略的に異なるゲーム状況の広範なカバレッジを提供します。
2. 拡張初期状態分布: DAGS は、混合分布 $\tilde{d}^\beta_0 = (1 - \beta)d_0 + \beta d_D$ を定義します。ここで、$d_0$ は元のルート分布、$d_D$ はオフラインデータセット上の一様分布です。パラメータ $\beta \in [0, 1]$ は、オフライン状態から開始するエピソードの割合を制御します。
3. 自己対戦との統合: 訓練中に、エピソードは $\tilde{d}^\beta_0$ からサンプリングされます。エピソードがオフライン状態から開始する場合、環境は元の遷移ダイナミクスに従って進化し続け、ゲームの情報構造を保持します。
4. 均衡バイアスの軽減: 著者は、不完全情報ゲームにおいて開始状態分布を変更すると、エージェントの私的情報に対する信念が歪み、バイアスのかかった均衡につながる可能性を特定しました。これを軽減するために、エピソードのソースを示すバイナリ観測フラグ（ルート開始の場合は $f=0$、データセット開始の場合は $f=1$）を用いたマルチタスク学習を採用します。これにより、ポリシーは元のゲーム（$f=0$）に対する不偏な戦略を学習しつつ、共有ネットワークパラメータを通じてデータセット開始エピソード（$f=1$）の拡張された探索を利用できます。

ベンチマーク構築

解析的に扱いやすい搾取可能性を伴う制御された環境で DAGS を評価するために、著者は OpenSpiel ゲーム（クーンポーカー、グーフスプレイ）に基づいた新しいベンチマーク環境のセットを導入しました。これらのベンチマークは、以下の 2 つの変換を適用します。

1. フォフェイト（FF）変換: 制御タスクの遂行失敗をモデル化するために、すべての意思決定ノードに厳密に支配された「フォフェイト」アクションを追加します。
2. 制御ゲーム変換: 各意思決定を多段階のグリッドワールドナビゲーションタスクに置き換えます。エージェントは時間制限内に特定の「アクションマス」に到達するためにグリッドをナビゲートする必要があります。正しいマスに到達できない場合、フォフェイトアクションがトリガーされます。
   これらの変換は、ポリシーをベースゲームに解析的に還元して正確な搾取可能性を計算できるようにしつつ、地平線と状態空間を大幅に増加させます。

主要な貢献

1. 新しいベンチマークスイート: 著者は、長期的な地平線と探索の課題（グリッドワールドナビゲーション）を有し、搾取可能性を解析的に計算できる 2 人ゼロ和（2p0s）ゲームのセットを提供します。これは、戦略的複雑性と扱いやすい評価を組み合わせるベンチマークの欠如に対処するものです。
2. DAGS による収束の加速: 本論文は、DAGS が正則化されたポリシー勾配アルゴリズム（具体的には PPO-Uniform および PPO-EMAg）が、固定された計算予算下で著しく大きな探索課題を伴うゲームにおいて、より低い搾取可能性を達成することを示しています。
3. 均衡バイアスの特定と軽減: この研究は、開始状態分布の拡張が不完全情報ゲームにおいて学習された均衡をバイアスさせる可能性があることを示しています。また、不偏なプレイを回復するためのマルチタスク観測フラグを用いた単純な軽減戦略を提供します。

実験結果

著者は、DAGS をクーンポーカー、4 カードグーフスプレイ、および均衡バイアスを露呈するように設計されたカスタム反例ゲームで評価しました。

• 探索のスケーリング: 「コントロールトラベル」バリアント（エージェントがアクションを実行するためにグリッドをナビゲートする必要があるもの）において、標準的な自己対戦（$\beta=0$）は時間制限内に特定のアクションマスにナビゲートする方法を発見できず、高い搾取可能性（事実上のフォフェイト）をもたらしました。DAGS（$\beta > 0$）は中間状態でエピソードを正常に初期化し、エージェントが高レベルの戦略的相互作用の解決に集中できるようにしました。高い難易度（トラベル 20）のグーフスプレイでは、標準的な自己対戦は高い搾取可能性でプラトーしましたが、DAGS は低い搾取可能性へと収束し続けました。
• 均衡バイアス: 反例ゲームにおいて、$\beta=1$（常にオフラインデータから開始）に設定すると、エージェントは隠れた情報に対する歪んだ信念により、高い搾取可能性を持つバイアスのかかった均衡に収束しました。
• 軽減の効果: 中間的な $\beta$（例：0.5）を使用し、タスクを識別する観測フラグと組み合わせることで、バイアスを正常に軽減しました。$f=0$ ブランチは元のゲームに対する不偏なポリシーを学習し、$f=1$ ブランチは探索を促進しました。このアプローチは、均衡の正確性を犠牲にすることなく効果的な探索を達成しました。

意義と主張

本論文は、DAGS が、長い制御シーケンスの探索コストと戦略的相互作用の学習コストを分離することにより、大規模な不完全情報ゲームを解決するための実用的な道筋を提供すると主張しています。オフラインデータをポリシーの初期化ではなく状態のカバレッジのために活用することで、DAGS は行動模倣よりも少ないデータを必要とし、デモンストレーションが不完全または非最適であっても実用可能です。

著者は、使用された特定のアルゴリズム（正則化された PPO）に関する貢献の範囲は限定的であるが、マルチエージェント設定における状態リセットに関する方法論的洞察において重要であると強調しています。開始分布の変更は単一エージェント RL では既知の技術ですが、不完全情報ゲームへの適用は、対処すべき固有の均衡バイアスのリスクをもたらすことを指摘しています。提案されたマルチタスク学習による軽減策は、この特定の課題に対する堅牢な解決策を提供します。

この研究は、現在のベンチマークが解析的な扱いやすさを維持するために単純なメカニズムを使用しているものの、DAGS の原則は、デモンストレーションが希少で行動模倣がデータ非効率的である複雑なドメイン（例：格闘ゲーム、FPS）にスケーリングすると結論付けています。著者は、正確な搾取可能性が扱い不可能なゲームにこれらの技術を適用する将来の作業において、DAGS を有望な方向性として位置付けています。