論文の概要: Identifying Copeland Winners in Dueling Bandits with Indifferences

• arxiv url: http://arxiv.org/abs/2310.00750v1
• Date: Sun, 1 Oct 2023 17:59:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 02:07:43.072556
• Title: Identifying Copeland Winners in Dueling Bandits with Indifferences
• Title（参考訳）: ディファレンスのあるバンドにおけるコペランドの勝者の同定
• Authors: Viktor Bengs, Bj\"orn Haddenhorst, Eyke H\"ullermeier
• Abstract要約: 本研究は,3次フィードバックを伴うデュエルバンディット問題において,コペランドの勝者を識別するタスクについて考察する。 我々は,Copeland の勝者を固定誤差確率で求める学習アルゴリズムに対して,サンプルの複雑性を低くする。 我々は,この下界とほぼ一致し,優れた経験的性能を示すサンプル複雑性を持つアルゴリズムPOCOWISTAを提案する。
• 参考スコア（独自算出の注目度）: 12.96903983663382
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of identifying the Copeland winner(s) in a dueling bandits problem with ternary feedback. This is an underexplored but practically relevant variant of the conventional dueling bandits problem, in which, in addition to strict preference between two arms, one may observe feedback in the form of an indifference. We provide a lower bound on the sample complexity for any learning algorithm finding the Copeland winner(s) with a fixed error probability. Moreover, we propose POCOWISTA, an algorithm with a sample complexity that almost matches this lower bound, and which shows excellent empirical performance, even for the conventional dueling bandits problem. For the case where the preference probabilities satisfy a specific type of stochastic transitivity, we provide a refined version with an improved worst case sample complexity.
• Abstract（参考訳）: 我々は,3次フィードバックによる決闘バンディット問題において,コープランド勝者を識別するタスクについて検討する。 これは、2つのアーム間の厳密な選好に加えて、無関心の形でフィードバックを観察することができる従来のデュエルリング・バンディット問題の、未発見だが実際は関係のある変種である。 本稿では,固定誤差確率のコープランド勝者を求める学習アルゴリズムに対して,サンプルの複雑性を低く評価する。 さらに,この下限にほぼ一致し,従来のデュエルリングバンディット問題においても優れた経験的性能を示すサンプル複雑性を持つアルゴリズムであるpocowistaを提案する。 選好確率が特定のタイプの確率推移性を満たす場合、より洗練されたバージョンを提供し、最悪のケースのサンプル複雑性を改善した。

関連論文リスト

• Neural Dueling Bandits [58.90189511247936]
  ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。 次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
  論文  参考訳（メタデータ） (2024-07-24T09:23:22Z)
• Multi-Player Approaches for Dueling Bandits [58.442742345319225]
  Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。 また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
  論文  参考訳（メタデータ） (2024-05-25T10:25:48Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• 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)
• Batched Dueling Bandits [13.69077222007053]
  そこで本研究では,2つの標準設定条件下で,K$アームのデュエルバンディット問題について検討した。 バッチ数と後悔数のトレードオフを円滑に行うアルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-02-22T04:02:36Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• Statistical Consequences of Dueling Bandits [0.0]
  マルチアーマッド・バンディットのフレームワークは、しばしば教育介入を評価するために使われてきた。 近年の研究では、学生が嗜好の誘惑を通じて質的なフィードバックを提供する方が有益であることが示されている。 我々は,従来の一様サンプリング法とデュエルバンディットアルゴリズムを比較し,デュエルバンディットアルゴリズムが累積後悔最小化時に良好に動作することを示すが,特定の状況下でのType-I誤差率の増大と消費電力の低減につながる。
  論文  参考訳（メタデータ） (2021-10-16T23:48:43Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Thompson Sampling for Bandits with Clustered Arms [7.237493755167875]
  理論的および実験的に、与えられたクラスタ構造をどのように活用すれば、後悔と計算コストを大幅に改善できるかを示す。 我々のアルゴリズムは、以前に提案されたクラスタ化された腕を持つバンディットのアルゴリズムと比較してよく機能する。
  論文  参考訳（メタデータ） (2021-09-06T08:58:01Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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