論文の概要: How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

• arxiv url: http://arxiv.org/abs/2610.10795v1
• Date: Wed, 07 Oct 2026 18:52:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:53.636045
• Title: How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
• Title（参考訳）: 異質性の下でのランク付けに何回繰り返しペアワイド比較が必要か?
• Abstract要約: 本研究では,ユーザやタスクによって嗜好が異なる場合のペアワイズ比較から,人口平均ユーティリティによるランキングモデルについて検討する。 本稿では,各ユーザ・タスク・コンテキストにおける繰り返し比較がどの程度必要で,ランキング回復に十分かを検討する。
• 参考スコア（独自算出の注目度）: 10.06142299434944
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires $Ω(1/Δ^2)$ repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using $O(\log(1/Δ))$ repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only $O(1)$ comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.
• Abstract（参考訳）: 本研究では,ユーザやタスクによって嗜好が異なる場合のペアワイズ比較から,人口平均ユーティリティによるランキングモデルについて検討する。 以前の研究では、任意の数のユーザ(Golz et al , 2025)であっても、ユーザ毎の単一の比較では、最も平均的なユーティリティの選択肢を特定するには不十分であることが示されている。 本稿では,各ユーザ・タスク・コンテキストにおける繰り返し比較がどの程度必要で,ランキング回復に十分かを検討する。 逆温度が固定された異種Bradley-Terryモデルの下では、ランキング回復を保証するために、1コンテキストあたり$Ω(1/Δ^2)$繰り返し比較を必要とする、単純MLEベースのアルゴリズムから始める。 次に、2つのMLEベースの変種と、$O(\log(1/Δ))$繰り返し比較を用いてランキングを復元するランダム化ロシアのルーレット型アルゴリズムを示し、この対数依存が最適であることを証明した。 この最悪のケースではありますが、ロシアのルーレットアルゴリズムは期待値当たりのO(1)$比較しか使用していません。 アリーナデータに基づく合成実験と半合成実験は、4つのアルゴリズムを好みの不均一性の異なるレベルと異なる文脈分布で比較する。

関連論文リスト

• Optimal Top-$k$ Identification from Pairwise Comparisons [0.0]
  雑音のあるペアワイズ比較から, 固定信頼トップ=k$識別の能動的学習問題について検討した。 この問題では、アイテムのペアを逐次選択して比較し、結果を観察し、エラー確率が最大$$$でトップ$k$アイテムのセットを返すことができる場合に停止する。
  論文  参考訳（メタデータ） (2026-07-09T22:55:16Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Ranking with Confidence for Large Scale Comparison Data [2.486161976966064]
  本研究では、比較ノイズを考慮した生成データモデルを用いて、ペア比較から高速で正確で情報的なランク付けを行う。 実データでは、PD-Rankは、アクティブな学習方法よりも同じKendallアルゴリズムを達成するのに、計算時間が少ない。
  論文  参考訳（メタデータ） (2022-02-03T16:36:37Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
  機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。 本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。 さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:35Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。