論文の概要: Non-Stationary Dueling Bandits Under a Weighted Borda Criterion

• arxiv url: http://arxiv.org/abs/2403.12950v2
• Date: Sat, 28 Sep 2024 15:05:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 22:01:26.160766
• Title: Non-Stationary Dueling Bandits Under a Weighted Borda Criterion
• Title（参考訳）: 太いボルダ条件下での非定常デュエルバンド
• Authors: Joe Suk, Arpit Agarwal,
• Abstract要約: 本稿では,BordaとCondorcetの両問題を一般化した新しい$textitweighted Borda score$ frameworkを紹介する。 また、ボルダ問題とコンドルセット問題の両方を一般化する新しい$textitweighted Borda score$ frameworkを導入する。
• 参考スコア（独自算出の注目度）: 11.770902693413401
• License:
• Abstract: In $K$-armed dueling bandits, the learner receives preference feedback between arms, and the regret of an arm is defined in terms of its suboptimality to a $\textit{winner}$ arm. The $\textit{non-stationary}$ variant of the problem, motivated by concerns of changing user preferences, has received recent interest (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023). The goal here is to design algorithms with low {\em dynamic regret}, ideally without foreknowledge of the amount of change. The notion of regret here is tied to a notion of winner arm, most typically taken to be a so-called Condorcet winner or a Borda winner. However, the aforementioned results mostly focus on the Condorcet winner. In comparison, the Borda version of this problem has received less attention which is the focus of this work. We establish the first optimal and adaptive dynamic regret upper bound $\tilde{O}(\tilde{L}^{1/3} K^{1/3} T^{2/3} )$, where $\tilde{L}$ is the unknown number of significant Borda winner switches. We also introduce a novel $\textit{weighted Borda score}$ framework which generalizes both the Borda and Condorcet problems. This framework surprisingly allows a Borda-style regret analysis of the Condorcet problem and establishes improved bounds over the theoretical state-of-art in regimes with a large number of arms or many spurious changes in Condorcet winner. Such a generalization was not known and could be of independent interest.
• Abstract（参考訳）: K$の武器を持つデュエルバンドでは、学習者はアーム間の好みのフィードバックを受け取り、アームの後悔は$\textit{winner}$のアームに最適化される。 この問題の$\textit{non-stationary}$ variantは、ユーザの好みを変えるという懸念から動機付けられ、近年の関心を集めている(Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023)。 ここでのゴールは、変化の量を知ることなく理想的に、低レベルの動的後悔を伴うアルゴリズムを設計することである。 ここでの後悔の概念は勝者の腕の概念と結びついており、典型的にはコンドルチェットの勝者かボルダの勝者と呼ばれる。 しかし、上記の結果はCondorcetの勝者に主に焦点が当てられている。 対照的に、この問題のボルダ版は、この研究の焦点である注意を減らしている。 最初に最適で適応的な動的後悔の上界 $\tilde{O}(\tilde{L}^{1/3} K^{1/3} T^{2/3} )$ を確立する。 また、ボルダ問題とコンドルセット問題の両方を一般化する新しい$\textit{weighted Borda score}$ frameworkを導入する。 この枠組みは、驚くほどにボルダ式のコンドルセット問題を後悔して分析することができ、多数の腕を持つ体制や多くのコンドルセット勝者の急激な変化を持つ体制において、理論上の最先端性に対する改善された境界を確立する。 そのような一般化は知られておらず、独立した関心を持つことができた。

関連論文リスト

• 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)
• Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation [50.469872635246176]
  我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。 このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
  論文  参考訳（メタデータ） (2023-11-27T09:19:01Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  線形帯域フィードバックによる逐次意思決定の問題点について検討する。 その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。 興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
  論文  参考訳（メタデータ） (2022-03-18T08:03:20Z)
• Bandit problems with fidelity rewards [7.154621689269006]
  フィデリティ・バンディット問題(英: fidelity bandits problem)とは、過去にプレイヤーがその腕に「ロヤル」したかによって、各腕の報酬がフィデリティ・報酬によって増強されるK$アームのバンディット問題の変種である。 忠誠ポイントモデルでは、余分な報酬の量は、これまで腕が演奏された回数に依存する。 サブスクリプションモデルでは、追加の報酬は腕の連続的な引き分けの数に依存する。
  論文  参考訳（メタデータ） (2021-11-25T11:09:43Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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