論文の概要: Replicable Dueling Bandits

• arxiv url: http://arxiv.org/abs/2610.20908v1
• Date: Wed, 14 Oct 2026 20:36:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:16.066509
• Title: Replicable Dueling Bandits
• Title（参考訳）: 複製可能なデュエルバンド
• Abstract要約: デュエルバンドは、初期のノイズの多い結果に基づいてそれぞれの比較を選択するので、同じ好みの2つの実行は異なるペアを比較することができる。 共振器について検討し,共振器内乱れと独立比較結果の2つの実行は,各ラウンドにおいて,少なくとも1-$の確率で同じ順序のペアを選択する必要がある。 線形デュエルバンディットに対して、後悔すべき$widetildeO(K2 H_mathrmp/2)$を達成するアルゴリズムを設計する。 合成および言語モデルの嗜好に関する実験は、サブ線形後悔を伴う複製性を示す。
• 参考スコア（独自算出の注目度）: 39.877009152322294
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Dueling bandits choose each comparison based on earlier noisy outcomes, so two runs on the same preferences can compare different pairs. We study replicable dueling bandits, where two executions with shared internal randomness and independent comparison outcomes must select the same ordered pair in every round with probability at least $1-ρ$. Building on Beat-the-Mean, whose scores change as arms are eliminated and need not rank the best arm highest, we design the first such algorithms with sublinear regret. Under relaxed stochastic transitivity with parameter $γ\ge 1$ and the stochastic triangle inequality, we design an algorithm that achieves expected regret $\widetilde{O}(γ^8 K^4 H_{\mathrm{p}}/ρ^2)$, where $H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}$. Under strong stochastic transitivity, we design an algorithm based on simultaneous elimination that improves the dependence on $K$ and achieves $\widetilde{O}(K^2 H_{\mathrm{p}}/ρ^2)$ regret. For linear dueling bandits, we design an algorithm that achieves regret $\widetilde{O}(d^3\sqrt{T}/(c_μρ))$. Experiments on synthetic and language-model preferences show replicability, with sublinear regret.
• Abstract（参考訳）: デュエルバンドは、初期のノイズの多い結果に基づいてそれぞれの比較を選択するので、同じ好みの2つの実行は異なるペアを比較することができる。 複製可能なデュエルバンディットについて検討し、内部ランダム性と独立比較結果の2つの実行は、各ラウンドで少なくとも1-ρ$の確率で同じ順序のペアを選択する必要がある。 Beat-the-Mean(ビート・ザ・ミーン)は、腕が取り除かれ、最高の腕をランク付けする必要がないため、サブリニアな後悔を伴う最初のアルゴリズムを設計する。 H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}$ で、パラメータ $γ\ge 1$ と確率的三角形の不等式を緩和した確率的推移性の下で、期待される後悔点 $\widetilde{O}(γ^8 K^4 H_{\mathrm{p}}/ρ^2)$ を達成するアルゴリズムを設計する。 強い確率的推移性の下で、K$への依存を改善して、後悔する$\widetilde{O}(K^2 H_{\mathrm{p}}/ρ^2)$を得る同時除去に基づくアルゴリズムを設計する。 線形デュエルバンディットに対して、後悔の$\widetilde{O}(d^3\sqrt{T}/(c_μρ))$を達成するアルゴリズムを設計する。 合成および言語モデルの嗜好に関する実験は、サブ線形後悔を伴う複製性を示す。

関連論文リスト

• Replicable Bandits with UCB based Exploration [26.974139987497818]
  我々は,UPB(Upper Confidence Bound)を用いたマルチアーム・バンディット(MAB)とリニア・バンディットの探索アルゴリズムについて検討した。 バンディットアルゴリズムが$$-replicable(英語版)であるとは、共用内部と独立の報酬実現を用いた2つの実行が、少なくとも1-$の確率で同じアクションシーケンスを生成することである。 我々はRepUCBが、後悔の$O!left(fracK2log2 T2sum_a:_a>0left(_a+fraclog(KTlog T)_に達することを示す。
  論文  参考訳（メタデータ） (2026-04-21T22:04:35Z)
• Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives [0.9749560288448116]
  学習者が1ラウンドあたり$m geq 2$のアームを選択し、勝者のみを観察し、ランキングシステムやレコメンデーションシステムを含む多くのアプリケーションで自然に発生する。 我々はCondorcetとBordaの両方の目的の下で,マルチダウリングバンディットのための初めてのベスト・オブ・ボス・ワールド・アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2026-03-19T14:38:52Z)
• Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
  本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。 我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。 我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2024-08-16T17:41:35Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Replicability in Reinforcement Learning [46.89386344741442]
  生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。 ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
  論文  参考訳（メタデータ） (2023-05-31T05:16:23Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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