論文の概要: Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives

• arxiv url: http://arxiv.org/abs/2603.18972v2
• Date: Fri, 20 Mar 2026 10:09:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 13:01:03.911475
• Title: Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives
• Title（参考訳）: ベスト・オブ・ボス・ワールド マルチ・ダウリング・バンド:コンドルチェットとボルダの目的の下での確率的・対数的選好のための統一アルゴリズム
• Authors: S Akash, Pratik Gajane, Jawar Singh,
• Abstract要約: 学習者が1ラウンドあたり$m geq 2$のアームを選択し、勝者のみを観察し、ランキングシステムやレコメンデーションシステムを含む多くのアプリケーションで自然に発生する。 我々はCondorcetとBordaの両方の目的の下で,マルチダウリングバンディットのための初めてのベスト・オブ・ボス・ワールド・アルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 0.9749560288448116
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-dueling bandits, where a learner selects $m \geq 2$ arms per round and observes only the winner, arise naturally in many applications including ranking and recommendation systems, yet a fundamental question has remained open: can a single algorithm perform optimally in both stochastic and adversarial environments, without knowing which regime it faces? We answer this affirmatively, providing the first best-of-both-worlds algorithms for multi-dueling bandits under both Condorcet and Borda objectives. For the Condorcet setting, we propose $\texttt{MetaDueling}$, a black-box reduction that converts any dueling bandit algorithm into a multi-dueling bandit algorithm by transforming multi-way winner feedback into an unbiased pairwise signal. Instantiating our reduction with $\texttt{Versatile-DB}$ yields the first best-of-both-worlds algorithm for multi-dueling bandits: it achieves $O(\sqrt{KT})$ pseudo-regret against adversarial preferences and the instance-optimal $O\left(\sum_{i \neq a^\star} \frac{\log T}{Δ_i}\right)$ pseudo-regret under stochastic preferences, both simultaneously and without prior knowledge of the regime. For the Borda setting, we propose $\texttt{SA-MiDEX}$, a stochastic-and-adversarial algorithm that achieves $O\left(K^2 \log KT + K \log^2 T + \sum_{i: Δ_i^{\mathrm{B}} > 0} \frac{K\log KT}{(Δ_i^{\mathrm{B}})^2}\right)$ regret in stochastic environments and $O\left(K \sqrt{T \log KT} + K^{1/3} T^{2/3} (\log K)^{1/3}\right)$ regret against adversaries, again without prior knowledge of the regime. We complement our upper bounds with matching lower bounds for the Condorcet setting. For the Borda setting, our upper bounds are near-optimal with respect to the lower bounds (within a factor of $K$) and match the best-known results in the literature.
• Abstract（参考訳）: 学習者が1ラウンドあたり$m \geq 2$の腕を選択し、勝者のみを観察するマルチダウリングの盗賊は、ランキングシステムやレコメンデーションシステムを含む多くのアプリケーションで自然に発生するが、根本的な疑問は未解決のままである。 我々はこれを肯定的に答え、CondorcetとBordaの両方の目的の下で、マルチ・ダウリング・バンディットのための初めてのベスト・オブ・ボス・ワールドズ・アルゴリズムを提供する。 In the Condorcet set, we propose $\texttt{MetaDueling}$, a black-box reduction that a dueling bandit algorithm into a multi-dueling bandit algorithm by transforming multi-way winner feedback into an unbiased pairwise signal。 $O(\sqrt{KT})$ pseudo-regret against adversarial preferences and the instance-optimal $O\left(\sum_{i \neq a^\star} \frac {\log T}{Δ_i}\right)$ pseudo-regret under the stochastic preferences, and both both both the prior knowledge of the regime。 Borda の設定に対しては、$O\left(K^2 \log KT + K \log^2 T + \sum_{i: Δ_i^{\mathrm{B}} > 0} \frac{K\log KT}{(Δ_i^{\mathrm{B}})^2}\right)$ 確率的環境における後悔と $O\left(K \sqrt{T \log KT} + K^{1/3} T^{2/3} (\log K)^{1/3}\right)$ 反逆に対して反逆的である。 上界をコンドルセットの一致した下界で補う。 ボルダ設定の場合、上界は下界に関してほぼ最適であり($K$の係数で)、文献の最もよく知られた結果と一致する。

関連論文リスト

• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback [39.83169162678798]
  本稿では,Best-Both-Worlds (BoBW) フレームワークにおいて,逆選択遅延を用いたマルチアームバンディット問題について検討する。 我々の主な貢献は、各設定の既知の下界を個別にマッチングする新しいアルゴリズムである。 これは$sum_i>0left(log T/Delta_iright) + frac1Ksum Delta_i sigma_max$で、$Delta_i$はarm $i$と$のサブ最適ギャップである。
  論文  参考訳（メタデータ） (2025-05-30T04:05:52Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では,両逆境における上界を後悔するEmphBest-of-Both-Worlds (BoBW) アルゴリズムを開発した。 提案アルゴリズムは限界条件下で$Oleft(log(T)1+beta2+betaTfrac12+betaright)$ regretを達成していることを示す。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
  そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。 私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
  論文  参考訳（メタデータ） (2021-02-19T11:03:51Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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