論文の概要: Adversarial Dueling Bandits

• arxiv url: http://arxiv.org/abs/2010.14563v1
• Date: Tue, 27 Oct 2020 19:09:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 11:31:26.110443
• Title: Adversarial Dueling Bandits
• Title（参考訳）: 敵対的デュエル・バンディット
• Authors: Aadirupa Saha, Tomer Koren, Yishay Mansour
• Abstract要約: 本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
• 参考スコア（独自算出の注目度）: 85.14061196945599
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the problem of regret minimization in Adversarial Dueling Bandits. As in classic Dueling Bandits, the learner has to repeatedly choose a pair of items and observe only a relative binary `win-loss' feedback for this pair, but here this feedback is generated from an arbitrary preference matrix, possibly chosen adversarially. Our main result is an algorithm whose $T$-round regret compared to the \emph{Borda-winner} from a set of $K$ items is $\tilde{O}(K^{1/3}T^{2/3})$, as well as a matching $\Omega(K^{1/3}T^{2/3})$ lower bound. We also prove a similar high probability regret bound. We further consider a simpler \emph{fixed-gap} adversarial setup, which bridges between two extreme preference feedback models for dueling bandits: stationary preferences and an arbitrary sequence of preferences. For the fixed-gap adversarial setup we give an $\smash{ \tilde{O}((K/\Delta^2)\log{T}) }$ regret algorithm, where $\Delta$ is the gap in Borda scores between the best item and all other items, and show a lower bound of $\Omega(K/\Delta^2)$ indicating that our dependence on the main problem parameters $K$ and $\Delta$ is tight (up to logarithmic factors).
• Abstract（参考訳）: 敵対的デュエル・バンディットにおける後悔の最小化の問題を紹介する。 古典的なDueling Banditsのように、学習者はアイテムのペアを何度も選択し、このペアに対して相対的なバイナリの ‘win-loss’ フィードバックのみを観察する必要があるが、このフィードバックは任意の選好行列から生成され、おそらく逆選択される。 我々の主な結果は、K$項目の集合から得られる 'emph{Borda-winner} に対して $T$-round regret が$\tilde{O}(K^{1/3}T^{2/3})$であり、一致する $\Omega(K^{1/3}T^{2/3})$ lower bound である。 私たちはまた、同様の高い確率の後悔境界を証明します。 さらに、より単純な \emph{fixed-gap} 逆向きの設定も検討し、これは2つの極端優先フィードバックモデル(定常選好と任意の選好列)をブリッジする。 ここでは、$\Delta$は、最良の項目と他のすべての項目の間のボルダのスコアのギャップであり、主な問題パラメータへの依存度が$K$と$\Delta$が(対数的要因まで)厳密であることを示す$\Omega(K/\Delta^2)の低い境界を示す。

関連論文リスト

• Adversarial Multi-dueling Bandits [0.4467766778351321]
  対戦型多段バンディットにおける後悔の問題について紹介する。 このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
  論文  参考訳（メタデータ） (2024-06-18T10:28:12Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
  本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。 本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
  論文  参考訳（メタデータ） (2022-06-07T08:22:56Z)
• Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback [10.179145161000315]
  複合匿名遅延フィードバックを用いた対向帯域幅問題について検討した。 この設定では、アクションの損失は$d$コンポーネントに分割され、アクションが選択された後に連続してラウンドが分散される。 損失シーケンスがメモリ境界である場合でも,$Omega(T)$疑似後悔が発生することを示す。
  論文  参考訳（メタデータ） (2022-04-27T08:32:35Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• 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)

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

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