技術要約：マルチユーザー・デュエリング・バンディット：ナッシュ社会厚生を用いた公平なアプローチ

問題定義

本論文は、**公平なマルチユーザー・デュエリング・バンディット（Fair Multi-User Dueling Bandit）**問題を取り扱う。これは、エージェントが $T$ のタイムホライズンと $K$ 個のアームに対し、$D$ 個の異なるユーザーから提供されるペア比較の嗜好データから学習する設定である。標準的なデュエリング・バンディットは、単一の嗜好モデルを想定するか、あるいは嗜好行列を単一のものに集約するが、本研究では、各ユーザー $d$ が潜在的に異なる嗜好行列 $P_d$ を持つシナリオを検討している。

核心となる課題は、これらの異質なユーザーの利益のバランスを取りつつ、マイノリティ・グループを疎外することなく、政策（ポリシー）を学習することである。平均（功利主義的）厚生を最適化する標準的な手法は、統計的な多数派を優遇しやすく、多様な嗜好を持つユーザーに対して不公平な結果を招く可能性がある。これに対処するため、著者らは、ユーザーの効用の積を最大化する**ナッシュ社会厚生（Nash Social Welfare: NSW）**を用いて目的関数を定義している。この目的関数は、本質的に不平等を抑制し、特定のユーザーの効用がゼロに近づくことを防ぐ。

重要な技術的障壁は、絶対的な報酬が存在せず、フィードバックが純粋に相対的（どちらのアームが好まれるかを示すバイナリの結果のみ）であることである。この相対的な設定において効用を定義するために、著者らは各ユーザーに対してコンドルセ勝者（Condorcet winner）（他のすべてのアームに対して確率 $>0.5$ で勝利するアーム）が存在すると仮定している。ユーザーの効用は、そのユーザー固有のコンドルセ勝者に対するアームの勝率から導出されるスコアとして定義される。

手法

理論的枠組み

著者らは、スコアリング関数 $s_d(i) = 2P_{d, i, a^*_d}$ （ここで $a^*_d$ はユーザー $d$ のコンドルセ勝者）を定義することで問題を定式化している。政策 $\pi$ のユーザー $d$ に対する効用は、期待スコア $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$ である。グローバルな目的関数はナッシュ社会厚生である：
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
目標は、この積を最大化する最適な政策 $\pi^*$ に対する期待累積リグレットを最小化することである。

困難性の解析

本論文は、$\Omega(T^{2/3} \min(K, D)^{1/3})$ という根本的なリグレットの下界を確立している。この結果は、相反するコンドルセ勝者を持つユーザー間でのNSWの最大化という要件が、標準的なデュエリング・バンディット（通常は $O(\log T)$ のリグレットを達成する）と比較して、大幅な困難さをもたらすことを示している。この困難さは、アルゴリズムが「良い」勝者を識別するために、「悪い」コンドルセ勝者（あるユーザーには最適だが、他のユーザーにとっては効用がほぼゼロになるもの）をプレイしなければならないという、探索コストと瞬間のリグレットとの間のトレードオフから生じる。

アルゴリズム

目的を達成するために、以下の2つのアルゴリズムが提案されている。どちらもコンドルセ勝者の特定フェーズを組み込んでいる。

1. Fair-Explore-Then-Commit (Fair-ETC):

   • フェーズ1（特定）: 修飾されたDvoretzky-Kiefer-Wolfowitz Tournament (DKWT) アルゴリズムを用いて、すべての $D$ ユーザーのコンドルセ勝者の集合 $\hat{A}^*$ を特定する。このフェーズは、共有された相互作用を利用して、すべてのユーザーの経験的なマージンを同時に更新する。
   • フェーズ2（探索）: 特定されたコンドルセ勝者に対するすべてのアームのスコアを推定する。
   • フェーズ3（コミットメント）: 経験的なNSWを最大化する政策 $\hat{\pi}$ を計算し、残りのホライズンに対してそれを実行する。

2. Fair-$\epsilon$-Greedy:

   • このアルゴリズムは、ホライズン全体を通じて探索と活用を交互に行う。
   • まず、上述と同じコンドルセ勝者の特定フェーズから始まる。
   • 各ステップ $t$ において、確率 $\epsilon_t$ で、スコア推定を精緻化するために（ラウンドロビン方式を用いて）コンドルセ勝者を含むペアをプレイすることで探索を行う。
   • 確率 $1-\epsilon_t$ で、現在の経験的NSWを最大化する政策をプレイすることで活用を行う。
   • 収束を確実にするため、探索率 $\epsilon_t$ は時間の経過とともに減衰する。

両アルゴリズムは、対数因子を除いて下界の $T$ への依存関係と一致する、$\tilde{O}(T^{2/3})$ のリグレット上界を達成することが証明されている。

主な貢献

1. 問題の定式化: 個別のコンドルセ勝者に基づくユーザー効用をモデル化し、公平性の目的としてNSWを採用した、公平なマルチユーザー・デュエリング・バンディット問題の最初の定式化。
2. リグレット下界: 異質な嗜好を持つデュエリング・バンディットにおける公平性のコストを定量化した最初の結果とされる、$\Omega(T^{2/3} \min(K, D)^{1/3})$ のリグレット下界の導出。
3. アルゴリズム的解決策: 下界の $T$ への依存関係と一致する理論的なリグレット上界を伴う、Fair-ETC および Fair-$\epsilon$-Greedy アルゴリズムの提案。
4. 実証的検証: 提案されたアルゴリズムが、公平性の指標（ジニ係数、最小ユーザー厚生）において功利主義的なベースラインを凌駕しつつ、競争力のある累積リグレットを維持することを実証する広範なシミュレーション。

実験結果

著者らは、ランダムに生成された嗜好および実世界のデータ（マクロなユーザーにクラスター化されたSushiデータセット）の両方でアルゴリズムを評価した。

• ランダムな嗜好: 様々なユーザー構成（$D$）およびアーム構成（$K$）において、Fair-ETC と Fair-$\epsilon$-Greedy は共に劣線形のリグレットを示し、功利主義的なベースラインおよびユーザー一様ベースラインを一貫して上回った。
• 公平性指標: 提案されたアルゴリズムは、功利主義的なアプローチと比較して、最も高いナッシュ社会厚生と著しく低いジニ係数を達成した。また、より高い最小ユーザー厚生を維持しており、マイノリティの嗜好をより良く保護していることを示している。
• クラスター化された嗜好: 明白な多数派と少数派のクラスターが存在するシナリオ（偏った嗜好をシミュレート）において、功利主義的なアルゴリズムは多数派を優遇し、高い不平等をもたらした。提案された公平なアルゴリズムは、低ジニ係数と高い最小厚生を維持しながら、利益のバランスを取ることに成功した。
• Sushiデータセット: 実世界のデータにおいて、提案手法は $D=5$ および $D=10$ のクラスター設定の両方で、最も低い累積リグレットを達成した。高度に断片化された $D=10$ のケースでは、一様ベースラインがわずかに優れた公平性を示したが、リグレットに関しては極めて劣っていた。

意義と主張

本論文は、異質な嗜好を持つデュエリング・バンディットにおける公平性のコストを定量化した最初の研究であり、$\Omega(T^{2/3})$ という根本的なリグレット下界を確立していると主張している。著者らは、平均的な嗜好を最適化することは不十分であり、マイノリティ・グループにとって有害である可能性があるため、本研究は人間中心の機械学習への必要なステップであると位置づけている。

ナッシュ社会厚生をデュエリング・バンディットの枠組みに統合することで、本研究は、効率性と公平性のバランスを取る政策を学習するための理論的およびアルゴリズム的な基礎を提供している。著者らは、絶対的な報酬ではなく相対的な嗜好の設定で動作するため、従来のマルチエージェント・バンディット（例：Hossain et al., 2021; Jones et al., 2023）とは根本的に異なる効用推定技術を必要とする点で、自身のアプローチが異なると述べている。

論文は、将来の研究において、コンテキスト付きデュエリング・バンディット、連続的なアクション空間、およびコンドルセ勝者の仮定が成立しない設定（おそらくコンドルセ法やボルダー法を使用する）への拡張が可能であることを認め、控えめに締めくくられている。