技術的概要：線形関数近似による大規模状態空間を有する頑健マルコフゲームにおけるマルチエージェントの呪いの克服

1. 問題定式化

本研究は、大規模または無限の状態空間を有する環境における**分布頑健マルチエージェント強化学習（MARL）の課題に取り組む。著者らは、2 つの重要な難しさを組み合わせた頑健線形マルコフゲーム（R-LMGs）**に焦点を当てている：

1. 頑健性： エージェントは、環境が規定された不確実性集合（具体的には全変動距離で定義される）内の名义モデルから逸脱した場合でも、最悪ケースのパフォーマンスを最適化しなければならない。
2. スケーラビリティ（マルチエージェントの呪い）： 標準的な MARL では、結合行動空間がエージェント数 $n$ に対して指数関数的に増大し、サンプル複雑性が $n$ に対して指数関数的にスケールする。これは状態空間が大規模または無限である場合に悪化し、表形式（tabular）手法の実用性を不可能にする。

既存の頑健マルコフゲーム（RMG）に対する証明可能な効率的なアルゴリズムは表形式の設定（有限の状態・行動空間）に限定されており、RMG に対する線形関数近似（LFA）に関する先行研究は唯一つ存在するが、これは（最小値が消失するという）制限的な仮定に依存しており、依然としてマルチエージェントの呪いに悩まされている。そこで本論文は問いかける：大規模状態空間を有する頑健マルコフゲームにおいて、マルチエージェントの呪いを克服できるか？

2. 手法

本論文は、生成モデル設定と新たに提案されたオンライン対話的設定という 2 つの異なるデータ収集メカニズムの下で、R-LMG に対する証明可能なデータ効率性の高いアルゴリズムを提案する。両方の設定は、各エージェントの遷移および報酬関数が、他のエージェントの行動とは独立した特徴ベクトル $\phi(s, a_i)$ の線形関数としてモデル化される**独立したエージェントごとの線形関数近似（LFA）**を利用する。

2.1 生成モデル設定

この設定では、アルゴリズムは任意の状態 - 行動対から名义遷移カーネル $P^0$ のサンプルを生成できるシミュレータにアクセスできる。

• アルゴリズム： L-Robust-Q-FTRL。
• 主要な革新（無限から有限への削減）： 網羅的なサンプリングを必要とする表形式手法とは異なり、著者らは Lemma 1（特徴空間の幾何学に基づく）から導出された分布 $\rho_i$ を用いて、状態 - 行動対の有限サポート集合（$Y_i$）を構築する。これにより、リッジ回帰を通じて（潜在的に無限の）状態空間全体のカバレッジを保証しつつ、$O(d^2)$ サイズの有限部分集合からのみサンプリングすることが可能になる。
• メカニズム： アルゴリズムは後方帰納法を実行する。各反復において、構築された有限集合からサンプリングし、リッジ回帰を通じて名义モデル（報酬と遷移）を推定し、頑健ベルマン方程式の双対形式を用いて頑健 Q 関数を更新する。方策の更新には、フォロウ・ザ・レギュラライズド・リーダー（FTRL）戦略を採用する。

2.2 オンライン対話的設定

この設定はより実用的であり、エージェントが環境と対話して軌道を収集する。主要な課題は、真の最悪ケース遷移カーネルが未知であり、不確実性集合のカーネルが必ずしも名义カーネルに対して仮定された線形構造を満たさないことである。

• アルゴリズム： Online-L-Robust-Q-FTRL。
• 主要な革新（ハイブリッドサンプリングと悲観的推定）：
  • 敵対者の近似： 真の最悪ケースカーネルが未知であるため、アルゴリズムは直接そこからサンプリングできない。代わりに、悲観的な頑健価値推定値の系列を導入する。これらの推定値は、不確実性集合内の「近似敵対環境」（定義 1）をクエリするために使用される。
  • ハイブリッドサンプリング戦略： 線形モデル推定の妥当性（これは名义カーネルにのみ適用される）を維持するため、アルゴリズムはハイブリッドサンプリング方式を使用する。軌道の最初の $h-1$ ステップでは、エージェントは近似敵対環境（悲観的推定値を使用）と対話する。最終ステップ $h$ では、名义カーネルからのサンプリングに切り替える。これにより、$h-1$ ステップまでの最悪ケースダイナミクスによって誘発される状態 - 行動占有分布を維持しつつ、最終遷移データが線形近似可能な名义モデルから得られることを保証する。
  • 双対推定値： アルゴリズムは、方策更新用の楽観的価値推定値と、敵対的サンプリングのガイダンス用の悲観的価値推定値の両方を維持する。これは、通常は楽観性のみに依存する標準的な線形 MG とは異なる点である。

3. 主要な貢献

1. 大規模状態空間におけるマルチエージェントの呪いの打破： 本論文は、大規模（無限を含む）状態空間を有する R-LMG に対して、マルチエージェントの呪いを打破する最初の証明可能なサンプル効率性の高いアルゴリズムを提供する。サンプル複雑性と後悔の上限は、結合行動空間 $\prod A_i$ ではなく、特徴次元 $d$ および最大個々の行動空間サイズ $\max_i A_i$ に対して多項式的に依存する。
2. 生成モデルの保証： 生成モデル設定の下で、提案アルゴリズムは $\tilde{O}(H^9 d^3 / \epsilon^4)$ のサンプル複雑性で $\epsilon$-近似粗相関均衡（CCE）を達成する。これは、不確実性集合の定式化に関わらず、生成モデル下での R-LMG に対する最初のそのような保証である。
3. オンライン対話プロトコル： 著者らは、エージェントが不確実性集合内の遷移カーネル（近似敵対環境）からサンプリングできる、実用的に意味のあるオンラインプロトコルを提案する。彼らは、アルゴリズムが $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$ の部分線形後悔を達成することを証明する。
4. 技術的新規性：
   • 無限から有限への削減： 頑健な設定において無限状態空間に一般化するために有限部分集合をサンプリングする手法。
   • ハイブリッドサンプリング： 不確実性集合の非線形性を克服しつつ、敵対環境の占有分布を維持しながら名义モデルを推定するための新たなメカニズム。
   • 悲観 - 楽観の双対性： 真の頑健価値が存在しない場合の敵対環境を近似するための悲観的価値推定値の導入。

4. 結果と理論的保証

• 生成モデル（定理 2）： アルゴリズムは、$N_{all} \ge O(H^9 d^3 / \epsilon^4)$ のサンプルを使用して、確率 $1-\delta$ で $\epsilon$-頑健 CCE を出力する。表形式への削減（$d = S \max A_i$）において、これは $\tilde{O}(H^9 S^3 (\max A_i)^3 / \epsilon^4)$ の複雑性をもたらす。これはすべてのパラメータに対して多項式的であり、先行する表形式の頑健手法における指数関数的依存性と対照的である。
• オンライン設定（定理 3）： アルゴリズムは $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$ の後悔上限を達成する。エピソード数 $T$ が $T > H^4 d^2 (\max_i A_i)^2 / \epsilon^2$ を満たす場合、出力は $\epsilon$-頑健 CCE となる。
• 比較： 結果は、線形 RMG に関する唯一の既存研究（Zheng and Lin, 2025）を大幅に上回る。この先行研究は、制限的な「最小値の消失」仮定を必要とし、マルチエージェントの呪い（$d_{curse} = S \prod A_i$）に悩まされていた。提案手法はこれらの制限を除去し、エージェント数に対する多項式的依存を達成する。

5. 意義と主張

著者らは、この研究が大規模（無限を含む）状態空間を有する頑健線形マルコフゲームに対して、マルチエージェントの呪いを成功裡に克服する最初の証明可能なサンプル効率性の高いアルゴリズムを提供すると主張する。

• 頑健性： この研究は、頑健 MARL の適用範囲を、小規模な表形式ドメインから、自動運転、ロボティクス、金融市場などの実世界応用に関連する大規模連続環境へと拡張する。
• データ効率性： エージェント数に対する指数関数的依存を打破することで、結合行動空間がそれ以外では処理不可能となるマルチエージェントシステムにおいて、頑健な学習を実行可能にする。
• 実用性： 近似敵対環境からのサンプリングを可能にする提案されたオンライン対話的設定は、安全クリティカルなアプリケーション（例えば、シミュレーションから実世界への転移、敵対的トレーニング）で使用される実用的なパラダイムと整合しており、部分線形後悔を達成するための問題の適切性を保証する。

本論文は、提案されたハイブリッドサンプリング戦略と悲観的価値推定値の使用が、頑健強化学習の将来の研究にとって独立した関心を持つ可能性のある主要な技術的貢献であると結論づけている。