Learning in Matching Games with Bandit Feedback

技術要約：マッチングゲームにおけるバンディットフィードバックを伴う学習

問題の定式化
本論文は、二部マッチング市場とゲーム理論が交差する領域における、新しい学習問題を紹介している。この設定では、一般化された市場において、$P$ と $A$ という2つの異なるエージェント集合が存在し、タイムホライゾン $T$ にわたって中央プラットフォームによってマッチングが行われる。エージェントが静的で既知の選好を持つ従来のマッチング問題や、エージェントが直接的な確率的報酬を受け取る標準的なマルチアームドバンディット（MAB）の設定とは異なり、このフレームワークでは、一度マッチングされると、エージェントは初期状態では未知の利得行列を持つ2人零和ゲーム（ZSG）に従事することを想定している。

このシナリオにおいて、エージェントは、これらの相互作用の結果から、潜在的なゲームのダイナミクスと自身の選好の両方を同時に学習しなければならない。各タイムステップ $t$ において：

1. 中央プラットフォームが、推定されたエージェントの選好に基づき、マッチング $m_t$ を生成する。
2. マッチングされたエージェントは、戦略（混合行動）を選択し、特定の行動をサンプリングする。
3. エージェントは確率的なバンディットフィードバック（報酬）を受け取り、マッチング相手の行動を観察する。
4. エージェントは、利得行列の推定値と次ラウンドのための選好を更新する。

核心となる課題は、**マッチング平衡（Matching Equilibrium）**を学習することである。これは [10] で定義された概念であり、マッチングが安定（ブロッキング・ペアが存在しない）であり、かつエージェントが割り当てられたパートナーに対してナッシュ平衡（NE）をプレイしている状態を指す。困難さは、エージェントが事前にはゲーム行列を知らず、選好を形成するために探索を行う必要がある一方で、マッチングメカニズム（通常はゲール＝シャプレー法）が、その選好に基づいて安定性を確保しようとする点にある。

手法とアルゴリズム
これに対処するため、著者らは「不確実性に直面した際の楽観主義（optimism in the face of uncertainty）」の原理に基づくアルゴリズムである UCB-MG を提案している。その手法は以下のように動作する：

• 楽観的な推定: エージェントは、潜在的なマッチ相手の利得行列に対して上側信頼限界（UCB）を保持する。具体的には、ペア $(p, a)$ に対して、観測された報酬の経験平均に信頼ボーナスを加えることで、推定利得行列 $\bar{A}_{p,a}$ が構築される。
• 選好の形成: これらの楽観的な利得行列に基づき、エージェントは各潜在的パートナーに対する最適プレイ（ミニマックス戦略）を仮定した、楽観的なゲーム価値（$\bar{V}^*$）を計算する。エージェントは、この楽観的なゲーム価値に従って選好をランク付けする。
• マッチング: 中央プラットフォームは、これらの報告された選好を収集し、現ラウンドの安定マッチングを生成するためにゲール＝シャプレー（GS）アルゴリズムを実行する。
• 戦略の実行: 一度マッチングされると、エージェントは楽観的な利得行列から導出されたミニマックス戦略に基づいて行動を選択し、行動をサンプリングし、フィードバックを受け取って推定値を更新する。

後悔の定式化：マッチング不安定性
本論文の重要な貢献は、**マッチング不安定性（Matching Instability: MI）**と呼ばれる適切な後悔（レグレット）指標の定義である。標準的なMABやゲーム理論の後悔の定義は、マッチングと戦略の結合平衡への収束が目標であるため、本設定には不十分である。

著者らは、現在のマッチング $m$ と戦略プロファイル $X$ が与えられたとき、市場を安定させるために必要な最小の総補助金を、MIとして定義している。数学的には、これは以下の制約条件下で補助金 $s_a$ を最小化する線形計画問題の解である：

1. ブロッキング・ペアの不在: 現在の戦略の下で、逸脱することで効用を改善できるペア $(p, a)$ が存在しないことを保証する。
2. 個人の合理性: エージェンドがマッチングされていない状態よりも、現在のマッチングを好むことを保証する。
3. 価値の保証: エージェントが、自身のゲームのミニマックス値と同等以上の効用を受け取ることを保証する（解析を容易にするための厳密なナッシュ条件の緩和）。

累積後悔 $R_T$ は、タイムホライゾン $T$ におけるマッチング不安定性の総和として定義される。

主な貢献

1. 学習問題の定義: 2部市場のエージェントが、マッチングのための選好を形成するために未知の零和ゲームを学習しなければならない、最初の学習設定を定式化した。
2. 後悔指標: マッチングが行われる設定において、Subset Instability [8, 17] の概念を拡張したマッチング不安定性を導入した。この指標は、マッチングされたエージェントがゲームをプレイする場合の、マッチング平衡からの距離を定量化する。
3. アルゴリズム設計: 楽観的なゲーム価値の推定とゲール＝シャプレー・メカニズムを統合した、UCBベースのアルゴリズム（UCB-MG）を提案した。
4. 理論的保証: 提案されたアルゴリズムが、タイムホライゾン $T$、各側のエージェント数 $p, a$、および各エージェントの行動数 $m, k$ に対して、インスタンスに依存しない劣線形の後悔境界 $\tilde{O}(\sqrt{Tmkpa})$ を達成することを証明した。
5. 汎用性: この理論的境界は既存の結果を統一している。$m=k=1$ のとき、古典的な二部マッチングの境界 $\tilde{O}(\sqrt{Tpa})$ を回収する。$p=a=1$ のとき、零和ゲームにおけるセルフプレイの境界 $\tilde{O}(\sqrt{Tmk})$ を回収する。

結果と実証的証拠
著者らは、利得行列が正規分布からサンプリングされる合成インスタンスを用いて、実証的な検証を行っている。彼らは以下の3つのシナリオを比較している：

• セルフプレイ (Self-Play): 両方の側がUCB-MGアルゴリズムに従う。
• ナッシュ・レスポンス (Nash-Response): 片方の側は真のゲーム行列を知っており、ナッシュ平衡戦略をプレイし、もう片方は学習を行う。
• ベスト・レスポンス (Best-Response): 片方の側は真の行列と相手の戦略を知っており、ベストレスポンスをプレイする。

結果は、すべてのシナリオにおいてシステムが安定した結果を学習し、劣線形な後悔の成長を示すことを示している。予想通り、ナッシュ・レスポンスのシナリオが最も低い後悔を実現した。興味深いことに、ベスト・レスポンスのシナリオは、初期段階ではセルフプレイよりも優れた性能を示すが、市場規模（エージェント数および行動数）が増大するにつれて、一方が他方を搾取することによる複雑さが増すため、性能が低下する。

意義と今後の方向性
本論文は、エージェントがゲーム内の行動を通じて直接的な選好信号を受け取るのではなく、ゲームを通じて相互作用した後にのみ利得を受け取る環境における学習を理解するための、第一歩としての意義を主張している。このような複雑で結合された設定においても、安定した結果を効率的に学習できることを示している。

著者らは、この研究を将来の研究の基礎として控えめに位置づけている。彼らはいくつかのオープンな方向性を特定している：

• モデルを零和ゲームから一般和ゲームへ拡張すること。
• 非零和のダイナミクスを扱うために、ノーレグレット学習アルゴリズム（Exp3など）をマッチングの枠組みに統合すること。
• エージェントが相手の行動を観察するという仮定を緩和すること。
• 代替的なゲームモデル（マルコフゲーム、スタッケルベルグゲーム）やマッチング構造（一対多のマッチング）を探索すること。
• 中央のコーディネーターなしに、エージェントがマッチングと戦略の両方を選択する分散型設定を調査すること。