論文の概要: The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits

• arxiv url: http://arxiv.org/abs/2603.15189v1
• Date: Mon, 16 Mar 2026 12:27:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 18:28:58.213986
• Title: The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
• Title（参考訳）: デュエルバンドにおけるコンドルチェット勝者同定のサンプリング複雑さ
• Authors: El Mehdi Saad, Victor Thuot, Nicolas Verzelen,
• Abstract要約: 本研究では,コンドルチェットの勝者が存在するという前提の下で,デュエルバンディットのベストアーム識別について検討する。 完全ギャップ行列 $_i,j=q_i,j-tfrac12$ を利用する新しい識別手順を導入する。 我々は、高確率、インスタンス依存のサンプル複雑度を導出し、(対数的要因を除いて)最もよく知られたものを改善することを保証します。
• 参考スコア（独自算出の注目度）: 6.244816393907942
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with probability at least $1/2$. We introduce a new identification procedure that exploits the full gap matrix $Δ_{i,j}=q_{i,j}-\tfrac12$ (where $q_{i,j}$ is the probability that arm $i$ beats arm $j$), rather than only the gaps between the Condorcet winner and the other arms. We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones by leveraging informative comparisons beyond those involving the winner. We complement these results with new lower bounds which, to our knowledge, are the first for Condorcet-winner identification in stochastic dueling bandits. Our lower-bound analysis isolates the intrinsic cost of locating informative entries in the gap matrix and estimating them to the required confidence, establishing the optimality of our non-asymptotic bounds. Overall, our results reveal new regimes and trade-offs in the sample complexity that are not captured by asymptotic analyses based only on the expected budget.
• Abstract（参考訳）: コンドルチェットの勝者が存在するという前提のもと、確率的デュエルバンディット(英語版)におけるベストアーム識別(英語版)、すなわち、少なくとも1/2$の確率で各ノイズのペア比較に勝つアーム(英語版)について研究する。 差分行列 $Δ_{i,j}=q_{i,j}-\tfrac12$(ここでは$q_{i,j}$は、コンドルチェットの勝者と他の腕の間の隙間だけではなく、アーム$i$がアーム$j$を打つ確率である)を利用する新しい識別手順を導入する。 我々は、高い確率、インスタンス依存のサンプル複雑度を導出し、(対数的要因を除いて)勝者を含むもの以上の情報的比較を活用することにより、最もよく知られたものを改善することを保証します。 我々はこれらの結果を新しい下界で補足するが、これは我々の知る限り、確率的デュエルバンディットにおけるコンドルチェット・ウィンナー識別の最初のものである。 我々の低バウンド分析は、ギャップマトリックス内の情報的エントリを抽出し、それらを要求された信頼度に推定する本質的なコストを分離し、非漸近的境界の最適性を確立する。 総じて, 予想される予算に基づく漸近的分析では得られない, サンプルの複雑さの新たな状況とトレードオフを明らかにした。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。 エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。 我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-03T15:10:08Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• 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)
• Covariance Adaptive Best Arm Identification [0.0]
  ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。 武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。 この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
  論文  参考訳（メタデータ） (2023-06-05T06:57:09Z)
• Top Two Algorithms Revisited [14.783452541904365]
  トップ2のアルゴリズムは、トンプソンサンプリングの多腕バンディットモデルにおける最高の腕識別への適応として現れた。 本稿では,トップ2手法の一般解析を行い,リーダーの望ましい特性,挑戦者,および腕の(おそらくは非パラメトリックな)分布を同定する。 提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップを,他の選択に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-06-13T09:03:24Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。 C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
  論文  参考訳（メタデータ） (2021-09-10T15:41:07Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)

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

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