技術要約：両側不確実性下における、おそらく正しい最適安定マッチング

1. 問題の定式化

本研究は、両側のエージェントの選好が当初未知である、二部マッチング市場における逐次的学習問題を取り扱う。設定は中央集権的であり、アルゴリズムは各タイムステップでマッチングを選択し、マッチングされたペアの潜在的な効用を反映した、ノイズを含む確率的な報酬を受け取る。これはセミバンディット・フィードバック構造に従う。

マッチングにおけるマルチアームドバンディット（MAB）文献で一般的な従来のレグレット最小化フレームワークとは異なり、本論文は純粋探索（pure exploration）の観点を採用している。目的は、有限の時間内に終了し、高い確率（$1-\delta$）で最適安定マッチング（具体的には$P$-最適安定マッチング）を出力するアルゴリズムを設計することである。

核心となる課題は、両側不確実性である。両方の側のエージェント（$P$と$A$）の選好ランキングが未知である。アルゴリズムは、すべてのエージェントの完全なランキングを再構築する必要はなくとも、これらの選好を効率的に学習しなければならない。なぜなら、完全なランキングの学習は多くの場合、サンプル効率が悪いためである。

2. 方法論と主要概念

2.1 部分的選好と遍在的安定マッチング

中心的な理論的革新は、完全なランキングではなく、部分的選好ランキングを利用することである。著者らは、Rastegariら [2014] によって導入された**遍在的安定マッチング（Pervasive Stable Matching: PSM）**の概念を活用している。

• マッチングが、ある部分的な選好プロファイルに対してPSMであるとは、その部分的なプロファイルのあらゆる可能な完全な精緻化（refinement）に対して、そのマッチングが最適安定マッチングであり続けることを指す。
• アルゴリズムの目標は、PSMを許容する有効な部分的選好プロファイルを特定することである。そのようなプロファイルが見つかれば、アルゴリズムはすべての選好の曖昧さを解決する必要なく、最適安定マッチングを特定したとして終了できる。

2.2 許容ギャップ（Admissible Gap）

サンプル複雑性を分析するために、本論文では許容ギャップ（$\Delta_F$）を定義する。真の完全なランキングにおける最も識別が困難なペアを考慮する標準的な最小報酬ギャップ（$\Delta_{min}$）とは異なり、$\Delta_F$は、すべての有効な部分的選好プロファイルにおける最小ギャップの最大値として定義される。

• $\Delta_F \ge \Delta_{min}$ である。
• 有効な部分的プロファイルに焦点を当てることで、アルゴリズムは潜在的に極小な$\Delta_{min}$への依存を回避でき、結果としてサンプル複雑性の境界を改善できる。

2.3 アルゴリズム

本論文ではいくつかのアルゴリズムを提案している：

1. 一様探索戦略（Uniform Exploration Strategies）：

   • アルゴリズムは、すべてのペアが一様にサンプリングされることを保証するために、最小マッチング被覆（二部グラフのエッジ彩色議論から導出）からマッチングをサンプリングする。
   • 解析対象となる2つのバリアントがある。一つは探索ラウンド数を決定するために$\Delta_{min}$を使用するもの、もう一つは$\Delta_F$を使用するものである。$\Delta_F$を用いたバリアントは、部分的選好について考察することがサンプル複雑性を大幅に削減できることを示している。

2. E-PSM（Elimination PSM：除去型PSM）：

   • 報酬ギャップの事前知識を必要としない適応的な除去アルゴリズム。
   • メカニズム： 平均報酬の信頼区間を維持する。信頼区間が互いに離れている場合、高確率で部分順序が確立されるため、ペアが除去される。
   • 停止ルール： 現在の部分的選好プロファイルがPSMを許容する（POSMアルゴリズムを用いて計算）と同時に、アルゴリズムは終了する。
   • 複雑性： サンプル複雑性の境界は$\Delta_F$に依存し、1ラウンドあたりにサンプリングされるマッチングの数を制限するためにエッジ彩色議論を利用する。

3. EE-PSM（Extended Elimination：拡張除去型PSM）：

   • 超安定マッチング（無差別を含むあらゆる精緻化の下でも安定なマッチング）を特定した際に、さらにペアを除去する拡張版。
   • これにより早期終了が可能になるが、この特定の拡張に関するサンプル複雑性の理論的保証は依然として未解決の問題であると論文内で注記されている。ただし、経験的な結果はメリットを示唆している。

4. レグレット最小化メタアルゴリズム：

   • 著者らは、E-PSMを探索フェーズとして実行した後に「コミット」フェーズを実行することで、純粋探索のアプローチをレグレット最小化へと拡張している。
   • これにより、二部設定における従来のExplore-Then-Commit（ETC）の結果よりも優れた、$\Delta_{min}$への依存を回避したレグレット境界が得られる。

3. 主要な貢献

1. 純粋探索における両側不確実性： 本研究は、先行研究（主に片側不確実性またはレグレット最小化に焦点を当てていたもの）を、両側不確実性を持つ環境かつ純粋探索の目的へと拡張した。
2. 部分的選好の活用： 最適安定マッチングの特定には、完全な選好順序の学習は不要であることを示している。PSMをターゲットにすることで、アルゴリズムはすべての選好ギャップを解決する必要なく、より早く終了できる。
3. 洗練されたサンプル複雑性：
   • 一様戦略および除去アルゴリズムに対する理論的境界が提供されており、これらは最小ギャップ$\Delta_{min}$ではなく、許容ギャップ$\Delta_F$に依存する。
   • 解析には、マッチングのサンプリングを効率的に扱うために、二部グラフにおけるエッジ彩色議論が用いられている。
4. レグレット境界： 本論文は、$\Delta_{min}$に依存しない、最適安定マッチングに関する両側不確実性下でのレグレット境界を初めて確立した。
5. 下界（Lower Bounds）： 組合せ論的MABの技術を用いて、サンプル複雑性の理論的な下界を確立し、問題固有の困難さを特徴づけている。

4. 結果と評価

4.1 理論的結果

• 一様戦略： 定理4.2は、$\Delta_F$を使用することで、サンプル複雑性の境界が$O(\frac{\ln(KN/\delta)}{\Delta_{min}^2})$から$O(\frac{\ln(KN/\delta)}{\Delta_{F}^2})$に減少することを示す。$\Delta_F$は$\Delta_{min}$よりも任意に大きくなり得るため、これは重要な理論的改善である。
• 除去アルゴリズム： 定理5.1は、有効な部分的プロファイルにおける逆二乗ギャップの和に比例する、E-PSMのサンプル複雑性境界を提供している。
• レグレット： 定理5.2は、$\Delta_{min}$への依存を回避するメタアルゴリズムのレグレット境界を提供しており、これは従来のETCアプローチにおける限界であった。

4.2 実証的結果

様々な市場規模（$n$）を持つランダムなインスタンスに対してシミュレーションが行われた：

• サンプル複雑性： 除去ベースのアルゴリズム（E-PSMおよびEE-PSM）は、一様サンプリングのベースライン（U, U-PSM）を大幅に上回った。
• 安定性： 除去戦略（E-NS）は、一様サンプリングと比較して、ランダムなインスタンス間でより安定したパフォーマンスを示した（一様サンプリングは高い変動性を示した）。
• 停止ルールの影響： E-NS（停止ルールなし）とE-PSM（PSMで停止）の比較は、PSMベースの停止基準によって達成されるサンプル複雑性の劇的な削減を浮き彫りにした。
• レグレット： 片側不確実性の設定（AETGS-Eとの比較用ベンチマークとして使用）において、E-PSMのアプローチは、適応的除去ベースラインよりも低い累積レグレットを達成した。特に、探索の再開を必要とするインスタンスにおいて顕著であった。

5. 意義と主張

著者らは、最適安定マッチングに焦点を当てることで、不確実性下におけるマッチングアルゴリズムを分析するためのより自然な枠組みを提供すると主張している。主な意義は、学習の目的を完全な選好の再構築から切り離したことにある。PSMを特定することが最適性に十分であることを示すことで、本論文は、完全なランキングの回復を必要とする手法よりも、アルゴリズムがより早く、より少ないサンプルで終了できることを証明している。

また、本研究は、二部市場におけるレグレット境界に関する文献の空白を埋めるものであると主張しており、最小報酬ギャップに依存しない初の境界を提供している。著者らは、拡張除去ルール（EE-PSM）については、経験的な結果は有望であるものの、この特定の拡張に関する形式的なサンプル複雑性の保証は依然としてオープンな理論的課題であると述べ、控えめな姿勢を示している。

最後に、論文は、導出された下界に一致するアルゴリズムの設計、およびTrack-and-Stop最適化問題の効率的な近似の開発が、今後の研究における重要な方向性であると指摘している。